O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Exercising it

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required