Huffman decoding (in Scala)

Question

I'm trying to write an algorithm to perform Huffman decoding. I am doing it in Scala - it's an assignment for a Coursera course and I don't want to violate the honor code, so the below is pseudocode rather than Scala.

The algorithm I have written takes in a tree tree and a list of bits bits, and is supposed to return the message. However, when I try it on the provided tree, I get a NoSuchElementException (head of empty list). I can't see why.

I know that my code could be tidied up a bit - I'm still very new to functional programming so I've written it in a way that makes sense to me, rather than, probably, in the most compact way.

def decode(tree, bits) [returns a list of chars]: {

    def dc(aTree, someBits, charList) [returns a list of chars]: {

        if aTree is a leaf: 

            if someBits is empty: return char(leaf) + charList
            else: dc(aTree, someBits, char(leaf) + charList)

        else aTree is a fork:

            if someBits.head is 0: dc(leftFork, someBits.tail, charList)
            else someBits is 1:  dc(rightFork, someBits.tail, charList)
        }

     dc(tree, bits, [empty list])

     }

Thanks in advance for your help. It's my first time on StackOverflow, so I probably have some learning to do as to how best to use the site.

Answer 1

If I understand it correctly, you want to go through forks (with directions from bits) until you will find a leaf. Then you are adding leaf value to your char list and from this point you want to repeat steps. If I am right, then you should pass original tree to your helper method, not a leftFork or rightFork, which are leafs now. So it would be something like:

if aTree is a leaf: 
    if someBits is empty: return char(leaf) + charList
    else: dc(tree, someBits, char(leaf) + charList)