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

Summary

We looked at lists, the basic data structures used for functional programming. We had a detailed look at how list algorithms work in the immutable, side-effect-free functional world.

We saw the notion of a persistent data structure wherein the original version of the data structure is never mutated. Instead, we created a new structure, reflecting the change. We saw many cases of node insertion and removal for both lists and binary trees.

All of this copying could be thought of as too expensive. However, as we saw, we shared as many nodes as possible with the original data structure. We need to copy nodes only when we need to preserve the original version.

We implemented lists in Scala with the view of studying persistence and sharing. We ...

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