This is why I love pattern matching in languages that support it - typing is just one of the things on which they can switch. As the Scala website puts it (paraphrasing), "Pattern matching is switch on steroids!"
Here is how you would return all leaf values in a binary tree in Scala:
case class Node
case class Fork(left: Node, right: Node) extends Node
case class Leaf(value: Int) extends Node
def getValues(node: Node): List[Int] = node match {
case f: Fork => getValues(f.left) ++ getValues(f.right)
case l: Leaf => List(l.value)
}
EDIT: Would actually be more idiomatic in Scala to extract the values from the case classes rather than just matching on type...yet another wonderful feature of pattern matching. Coded as follows:
def getValues(node: Node): List[Int] = node match {
case Fork(left, right) => getValues(left) ++ getValues(right)
case Leaf(value) => List(value)
}
Here's the tail-call optimized version, won't blow the stack. Technically idiomatic, but way too cryptic to be serious code. Clearly I need more outlets for writing Scala. =)
@tailrec
def getValuesFromNode(node: Node, accValues: List.empty[Int], nodeList: List.empty[Node]): List[Int] = node match {
case Fork(left, right) => getValuesFromList(accValues, nodeList ++ List(left, right))
case Leaf(value) => getValuesFromList(accValues ++ List(value), nodeList)
}
@tailrec
def getValuesFromList(accValues: List.empty[Int], nodeList: List.empty[Node]): List[Int] = nodeList match {
case x :: xs => getValuesFromNode(x, accValues, xs)
case _ => accValues
}
Here is how you would return all leaf values in a binary tree in Scala:
EDIT: Would actually be more idiomatic in Scala to extract the values from the case classes rather than just matching on type...yet another wonderful feature of pattern matching. Coded as follows: