Huffman decoding. FP/Scala solution to TopCoder problem http://community.topcoder.com/stat?c=problem_statement&pm=6477&rd=9988

HuffMannDecode.scala

//http://community.topcoder.com/stat?c=problem_statement&pm=6477&rd=9988
object HuffMannDecode {

  abstract class BinTree {
    def add(repr: List[Char], c:Char): BinTree = {
	  	def add(tree: BinTree, repr: List[Char], c:Char): BinTree = {
	  		(repr, tree) match {
	  			case (Nil, EmptyTree) => Leaf(c)
	  			case ('0'::tail, EmptyTree) => Node(add(EmptyTree,tail,c),EmptyTree)
	  			case ('1'::tail, EmptyTree) => Node(EmptyTree, add(EmptyTree,tail,c))
	  			case ('0'::tail, Node(left, right)) => Node(add(left,tail,c),right)
	  			case ('1'::tail, Node(left, right)) => Node(left, add(right,tail,c))
	  		}
	  	}
	  	add(this, repr, c)
	  }
  }
  
  case class Node(left: BinTree,  right:BinTree) extends BinTree
  case class Leaf(value: Char) extends BinTree
  object EmptyTree extends BinTree
  
  object BinTree {
  	def apply():BinTree = EmptyTree
  }
  
  def decodeHuffman(encoded:String, tree:BinTree):String = {
  	def decode_i(chars:List[Char], node: BinTree):List[Char] = {
  		(chars, node) match {
  		  case (Nil, Leaf(c)) =>  List(c)
  		  case (Nil, _) =>  List()
  			case (l, Leaf(c)) =>  c::decode_i(l, tree)
  			case ('0'::tail, Node(left,right)) =>  decode_i(tail, left)
  			case ('1'::tail, Node(left,right)) =>  decode_i(tail, right)
  		}
  	}
  	val dec = decode_i(encoded.toList, tree)
  	dec.mkString
  }
  def decode(archive:String, dictionary: Array[String]): String = {
  	val dictionaryWithLetters = dictionary.zip('A' to ('A'+dictionary.length).toChar)
  	val decodeTree = dictionaryWithLetters.foldLeft(BinTree())( {case (tree,(str,letter)) => tree.add(str.toList,letter)})
  	decodeHuffman(archive, decodeTree)
  }
  // Example
  val dict = Array("110","011","10","0011","00011","111","00010","0010","010","0000")
  val data = "001101100101100110111101011001011001010"
  decode(data, dict)                              //> res0: String = DBHABBACAIAIC
}