哈斯克尔 - Huffman解码而不树

Question

因此，对于他们给了我一个任务，我有三个函数来完成，它们是从给定树的每个叶节点提取HCodeMap，将字符串编码成位的名单，并将该字符串解码回字符串。

我已经成功地完成代码提取和编码功能，但我努力使与上次解码功能的进步，因为我们不允许遍历树，因为我们没有给出一个使用。

这是我们与所提供的功能的格式，其次是一些类型：

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”。

我真的如何实际投入的函数然而，这挣扎。

我希望我没有做这个太混乱了，感谢您的帮助提前！

Answer 1

尝试连续解析所有代码，然后在成功匹配后重复。重复，直到没有更多的输入。

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