First i have type declaration for binary tree:
sealed trait BT[+A] case object Empty extends BT[Nothing] case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A];; And further i have this code for inorder traversal with this mystery looking operator " ::: ".
What does this operator " ::: " exactly mean in this code?
def inorder[A](tree: BT[A]): List[A] = { tree match { case Node(v,l,r) =>(inorder(l)) ::: (v::(inorder(r))) case Empty => Nil } } It is a method of scala.collection.immutable.List and what it does is concatenate lists. Example:
scala> List(1,2) ::: List(3,4,5) res0: List[Int] = List(1, 2, 3, 4, 5) See the API documentation.
Note this special thing: when a method name ends in :, then Scala calls the method on the value on the right, passing the value on the left as an argument (with other methods whose names do not end with :, it's the other way around). The API docs say "Adds the elements of a given list in front of this list", that's because the ::: method is called on List(3,4,5), with List(1,2) as an argument; so List(1,2) is added in front of List(3,4,5).
