Scala functional programming operator :::

Question

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
  }
}

Answer 1

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).