CODEWITHSUNDEEP
haskellrecursionfunctional-programminghuffman-code
tacotac1999
tacotac1999

Reputation: 21

Non exhaustive pattern error when decoding Huffman tree?

I'm trying to turn a Huffman tree and a stream of bits into a list of characters plus a boolean indicating whether or not the output consumed all the input bits. Here's an example:

decode xyz_code [True,False,True,True,True,False,False,True] = 
("yzyx",False)

Here's what I have so far, but it doesn't work. What's going wrong? Help!

data BTree a = Leaf a | Fork (BTree a) (BTree a) deriving (Show, Eq)

decode :: BTree a -> [Bool] -> ([a], Bool)
decode _ [] = ([],True)
decode (Leaf v) [bs] = ([v], bs)
decode (Fork left right) (b:bs)
   | b         = decode right bs
   | otherwise = decode left bs

Upvotes: 2

Views: 73

Answers (2)

Ry-
Ry-

Reputation: 224962

  • _ [] covers empty lists
  • (Fork left right) (b:bs) covers non-empty lists for Forks
  • (Leaf v) [bs] covers lists of length 1 for Leafs

So what’s missing that the compiler is warning you about? Lists of length > 1 for Leafs. You need to define this case as something. If reaching that state isn’t logically valid, an error is okay:

data BTree a = Leaf a | Fork (BTree a) (BTree a) deriving (Show, Eq)

decode :: BTree a -> [Bool] -> ([a], Bool)
decode _ [] = ([], True)
decode (Leaf v) [bs] = ([v], bs)
decode (Leaf v) _ = error "Too much code left at leaf"
decode (Fork left right) (b:bs)
   | b         = decode right bs
   | otherwise = decode left bs

Upvotes: 1

Mark Seemann
Mark Seemann

Reputation: 233170

The title seems to indicate that you get a warning about an incomplete pattern-match. Consider it:

58567334.hs:6:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for `decode': Patterns not matched: (Leaf _) (_:_:_)
  |
6 | decode _ [] = ([],True)
  | ^^^^^^^^^^^^^^^^^^^^^^^^...

It says that the pattern that involves any Leaf with a list of Booleans longer than two isn't covered.

The first pattern that matches on [] matches the empty list.

The next pattern that matches on [bs] matches on a list with a single element called bs. This is a common mistake.

You probably want this pattern instead:

decode (Leaf v) bs = -- ...

where bs is a [Bool] value (i.e. a list of Boolean values).

Now you have to figure out how to aggregate that list of Boolean values to a single Bool.

Upvotes: 1

Related Questions