How to store tree during recursion? (Huffman decoding)

Question

I'm trying to learn Haskell. I am trying to implement a Huffman Tree. The parameters of my decode function are (basically, the 'signature'):

decode :: HTree -> [Int] -> [Char]

So, given the tree, and a list of numbers, I want to return the decoded message. Suppose a = 01, b = 1, c = 001, d = 000.

I know how to do it when I can use two trees for decoding. i.e:

decode :: HTree -> HTree -> [Int] -> [Char]

Concisely put, keep the first tree as the original tree, and make the other tree go left or right based on the next number in [Int] (if it's 0, go left, if it's 1, go right). Repeat this until a leaf is reached, and then add the leaf into the list of [Char] and continue using recursion. However, I am trying to do this with just one tree, i.e:

decode :: HTree -> [Int] -> [Char]

but I can't see how to store the original HTree as I traverse through it looking for a leaf. I there a way to do this in haskell?

Answer 1

Just write a recursive helper function that has access to the original tree:

decode :: HTree -> [Int] -> [Char]
decode orig = go orig
  where go :: HTree -> [Int] -> [Char]
        go curr = -- use both orig and curr here