Haskell - Huffman Decoding without tree

Question

So for an assignment I have been given, I had three functions to complete, those being to extract an HCodeMap from each leaf node of a given tree, to encode a string into a list of Bits, and to decode that string of bits back into a string.

I have successfully completed the code extraction and encoding functions, but I am struggling to make progress with the last decoding function as we are not allowed to traverse a tree as we are not given one to use.

This is the format of the function, followed by some of the types we are supplied with:

decode :: [Bit] -> HCodeMap -> Maybe String 
data Bit = Zero | One deriving (Show, Eq)
type HCodeMap = [(Char, [Bit])]

I initially tried creating my own lookup function, which would swap the values of the HCodeMap, and then to lookup the first n bits from the list of Bits we are given.

I will use an example to demonstrate if I have not made myself very clear:

[Bit] we are given : [One,Zero,One,One,Zero]

HCodeMap we are given: [('c',[Zero]),('a',[One,Zero]),('b',[One,One])]

I planned to take the first bit we are given from the list, being One, and then to search through HCodeMap testing to see if that was equal to any of the [Bit]s there.

This is where my reverse lookup function would come in, as I could lookup the list of bits within the HCodeMap, as I cannot lookup by letter. It was along the lines of:

lookup (bits we are given here) (each tuple of HCodeMap) $ map swap code

In this case, we see that One does not match any of the HCodeMap tuples, so I then test One,Zero. This matches with 'a', so I add 'a' to a string, and then carry on with the next [Bit] we are passed, being One again.

etc etc this goes on and we are left with the string "abc".

I am really struggling with how to actually put this into a function however.

I hope I have not made this too confusing, thanks for any help in advance!

• András Kovács: Why not just reconstruct the tree from the HCodeMap?
• Gavin89: Unfortunately all of our tree creation functions require a string for their input, and also we were asked not to recreate all of them using a different input.

Answer 1

Try parsing all codes successively, then repeat after a successful match. Repeat until there's no more input.

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

For those who are unfamiliar with msum, here's its implementation specialized to Maybe:

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

• Gavin89: Ahh, I knew I had been doing something wrong! The act of just recursively calling a function on the next elements makes SO much more sense than trying to keep creating a longer list! Managed to get it all working! Thank you! :)