2015-01-04 86 views
1

因此,對於他們給了我一個任務,我有三個函數來完成,它們是從給定樹的每個葉節點提取HCodeMap,將字符串編碼成位的名單,並將該字符串解碼回字符串。哈斯克爾 - Huffman解碼而不樹

我已經成功地完成代碼提取和編碼功能,但我努力使與上次解碼功能的進步,因爲我們不允許遍歷樹,因爲我們沒有給出一個使用。

這是我們與所提供的功能的格式,其次是一些類型:

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

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

我最初嘗試創建自己的查找功能,這將交換HCodeMap的值,然後從我們給出的位列表中查找前n位。

我將用一個例子來說明,如果我沒有說得很清楚:

[位]我們得到:一,零,一,一,零]

HCodeMap我們給出:[('c',[Zero]),('a',[One,Zero]),('b',[One,One])]

我計劃先走我們從列表中獲得,作爲One,然後通過HCodeMap測試進行搜索,看看它是否與任何[Bit]相同。

這是我的反向查找功能會進來,因爲我可以在HCodeMap內查找位的名單,因爲我不能用字母查找。它是沿着線:

查找(位我們這裏給出)(HCodeMap的每個元組)$地圖交換代碼

在這種情況下,我們看到的是一個不匹配任何HCodeMap的元組,所以我然後測試One,Zero。這與'a'匹配,所以我給字符串加'a',然後繼續下一個我們通過的[Bit],再次是One。

等等等等這樣下去,我們留下了字符串「abc」。

我真的如何實際投入的函數然而,這掙扎。

我希望我沒有做這個太混亂了,感謝您的幫助提前!

+2

爲什麼不直接從'HCodeMap'重建樹? – 2015-01-04 12:18:26

+0

不幸的是,我們所有的樹形函數都需要一個字符串來輸入,而且我們被要求不要使用不同的輸入重新創建它們。 – Gavin89 2015-01-04 12:34:42

回答

3

嘗試連續解析所有代碼,然後在成功匹配後重復。重複,直到沒有更多的輸入。

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 

對於那些誰不熟悉msum,這裏是它的實現專門用於Maybe

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

啊,我知道我一直在做錯事!在下一個元素上遞歸調用一個函數的行爲使得它比試圖創建一個更長的列表更有意義!管理得到它所有的工作!謝謝! :) – Gavin89 2015-01-04 15:24:10