Book Image

Haskell Data Analysis Cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis Cookbook

By: Nishant Shukla

Overview of this book

Table of Contents (19 chapters)
Haskell Data Analysis Cookbook
Credits
About the Author
About the Reviewers
www.PacktPub.com
Preface
Index

Decoding a Huffman code


This code relies heavily on the previous recipe, Encoding a string using a Huffman tree. The same Huffman tree data structure is used next to decode a string representation of a Huffman coding.

Getting ready

Read the previous recipe, Encoding a string using a Huffman tree. The same HTree data structure is used in this recipe.

How to do it...

We traverse down the tree until we hit a leaf node. Then, we prepend the character found and restart from the root node. This process continues until no input is available:

decode :: String -> HTree -> String
decode str htree = decode' str htree
  where  decode' "" _ = ""
      decode' ('0':str) (HTree _ l _)
        | leaf l    = value l : decode' str htree
        | otherwise = decode' str l
      decode' ('1':str) (HTree v _ r)
        | leaf r    = value r : decode' str htree
        | otherwise = decode' str r
      leaf tree = left tree == Null && right tree == Null

See also

To encode data using a Huffman tree, see...