Haskell

Question

因此，对于给我的作业，我需要完成三个函数，即从给定树的每个叶节点中提取 HCodeMap，将字符串编码为位列表，以及对其进行解码一串比特回到一个字符串。

我已经成功完成了代码提取和编码功能，但我正在努力进行最后一个解码功能，因为我们不允许遍历树，因为我们没有使用。

这是函数的格式，后面是我们提供的一些类型：

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

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

我最初尝试创建自己的查找函数，它会交换 HCodeMap 的值，然后从给定的位列表中查找前 n 位。

没说清楚我再举个例子来说明：

[Bit] 我们得到：[一，零，一，一，零]

HCodeMap 我们得到：[('c',[Zero]),('a',[One,Zero]),('b',[一，一])]

我计划从列表中获取我们给出的第一位，即 One，然后通过 HCodeMap 测试进行搜索，看看它是否等于那里的任何 [Bit]。

这是我的反向查找功能的用武之地，因为我可以查找 HCodeMap 中的位列表，因为我不能按字母查找。它是沿着：

lookup (bits we given here) (HCodeMap的每个元组) $ map swap code

在这种情况下，我们看到 One 不匹配任何 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

Haskell - 没有树的霍夫曼解码

Haskell - Huffman Decoding without tree

decoding

huffman-code