It would be tedious to insert nodes manually to incrementally build a tree. Instead, we use folding to fold a list and accumulate the BST as a result.
We use the foldLeft
idiom a lot to build other data structures too. Here is how we could sum up a List[Int]
:
scala> val l = List(1,2,3,4) l: List[Int] = List(1, 2, 3, 4) scala> l.foldLeft(0)((acc, x) => acc + x) res33: Int = 10
The method has a curried form. It takes an initial value 0
and a function. It keeps invoking the function for each value of the list. The updated value of the accumulator is passed for each function invocation.
Here's a quiz for you: Could you multiply the numbers instead of summing them up? Please see https://coderwall.com/p/4l73-a/scala-fold-foldleft-and-foldright for more information:
scala> def empty[A](): Dictionary[A] = Leaf empty: [A]()Dictionary[A]
The empty
method indicates an empty BST, which is just a Leaf
. This forms our initial value for foldLeft
:
scala> val list = List...