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

The accumulator idiom

These methods are easy to understand. However, for unbalanced trees, concatenating long lists could be slow, very slow.

We could eliminate list concatenation by sending the result list as an accumulator argument:

scala>   def preorderAcc[A](tree: BinTree[A], acc: List[A]): List[A] = tree match { 
     |     case Leaf => acc 
     |     case Branch(v, l, r) => v :: preorderAcc(l, preorderAcc(r, acc)) 
     |   } 
scala> println(preorderAcc(t, Nil)) 
List(1, 2, 5, 9) 

The method now takes an additional argument: acc. We always set it to Nil when we call the method.

As in preorder, we have two cases.

The first clause is as follows:

case Leaf => acc 

This just returns the already accumulated values, if any.

The second clause is as follows:

case Branch(v, l, r) => v ...

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