하스켈 - 허프만 디코드 (트리 제외)

Question

주어진 과제에 대해 주어진 트리의 각 리프 노드에서 HCodeMap을 추출하고, 문자열을 비트 목록으로 인코딩하고, 그 비트 열을 다시 문자열로 디코딩하는 것입니다.

코드 추출 및 인코딩 기능을 성공적으로 완료했지만 사용 권한이 주어지지 않았기 때문에 마지막 디코딩 기능을 사용하여 트리를 트래버스하지 못하게되었습니다.

이

우리가 함께 제공되는 형식 중 일부 다음 함수의 형식입니다 :

내가 처음 HCodeMap의 값을 바꿀 것입니다 내 자신의 검색 기능을 만드는 시도

decode :: [Bit] -> HCodeMap -> Maybe String 

data Bit = Zero | One deriving (Show, Eq) 
type HCodeMap = [(Char, [Bit])] 

다음 주어진 비트 목록에서 처음 n 비트를 검색합니다. 나 자신이 매우 분명하게하지 않은 경우

나는 보여주기 위해 예를 사용합니다 :

은 [비트] 우리는 주어진 : [대, 0, 1, 하나, 제로]

HCodeMap을

나는 첫 번째 계획을 세울 계획이다. (예 : 우리는 목록에서 주어진 One, One, HCodeMap 테스트를 통해 검색하여 [Bit] 중 하나와 동일한 지 확인합니다.

문자로 조회 할 수 없기 때문에 HCodeMap 내의 비트 목록을 조회 할 수 있으므로이 위치에 내 역순 조회 기능이 제공됩니다. 그것은의 라인을 따라했다 :이 경우

조회 (우리가 여기에 주어진 비트) (HCodeMap의 각 튜플) $지도 스왑 코드

, 우리는 하나는 HCodeMap 일치하지 않는 것을 볼 수 튜플, 그래서 나는 One, Zero를 테스트한다. 이것은 'a'와 일치하므로 'a'를 문자열에 추가 한 다음 다음 [Bit]를 계속 수행하여 전달됩니다. 다시 One이됩니다.

등 기타 등등이 계속되며 문자열 "abc"가 남습니다.

저는 실제로 이것을 어떻게 함수에 넣을지 정말 고민하고 있습니다.

나는 이것을 너무 혼란스럽게 만들지 않았 으면 좋겠다. 사전에 도움을 주셔서 감사합니다!

Answer 1

모든 코드를 연속적으로 분석하고 일치가 성공한 후에 다시 시도해보십시오. 더 이상 입력이 없을 때까지 반복하십시오. msum에 익숙하지 않은 사람들을 위해

import Control.Monad 

data Bit = Zero | One deriving (Show, Eq) 
type HCodeMap = [(Char, [Bit])] 

decode :: [Bit] -> HCodeMap -> Maybe String 
decode bits codes = process bits where 

    -- if the code matches the input, return the corresponding 
    -- Char value along with the rest of of the input 
    match :: (Char, [Bit]) -> [Bit] -> Maybe (Char, [Bit]) 
    match (v, xs) ys = go xs ys where 
    go (x:xs) (y:ys) | x == y = go xs ys 
    go []  ys    = Just (v, ys) 
    go _  _    = Nothing 

    -- match and consume until there's no more input, or fail if there is no match. 
    -- note that msum takes the first Just from a list of Maybe-s, 
    -- or returns Nothing if there isn't any 
    process :: [Bit] -> Maybe String 
    process [] = Just [] 
    process xs = do 
    (v, xs) <- msum $ map (`match` xs) codes 
    (v:) `fmap` process xs 

는 여기 구현은 Maybe에 전문있어 :

msum :: [Maybe a] -> Maybe a 
msum (Just a:xs) = Just a 
msum (Nothing:xs) = msum xs 
msum []   = Nothing