Preface

This book is about functional algorithms and data structures. Algorithms and data structures are fundamentals of computer programming.

I started my career writing C and C++ code. I always enjoyed designing efficient algorithms. I have experienced many an Aha! moments, when I saw how powerful and creative pointer twiddling could be!

For example, reversing a singly linked list using three node pointers is a well known algorithm. We scan the list once and reverse it by changing the pointer fields of each node. The three pointer variables guide the reversal process. 

I have come across many such pointer tricks and have used them as needed.

I was next initiated into the world of multi-threading! Variables became shared states between threads! My bagful of tricks was still valid; however, changing state needed a lot of care, to stay away from insidious threading bugs.

The real world is never picture perfect and someone forgot to synchronize a data structure.

Thankfully we started using C++, which had another bagful of tricks, to control the state sharing. You could now make objects immutable!

For example, we were able to implement the readers/writer locking pattern effectively. Immutable objects could be shared without worry among thousands of readers!

We slept easier, the code worked as expected, and all was well with the world!

I soon realized the reason it worked well! Immutability was finally helping us better understand the state changes!

The sands of time kept moving and I discovered functional programming.

I could very well see why writing side-effect free code worked! I was hooked and started playing with Scala, Clojure, and Erlang. Immutability was the norm here.

However, I wondered how the traditional algorithms would look like in a functional setting--and started learning about it.

A data structure is never mutated in place. Instead, a new version of the data structure is created. The strategy of copy on write with maximized sharing was an intriguing one! All that careful synchronization is simply not needed!

The languages come equipped with garbage collection. So, if a version is not needed anymore, the runtime would take care of reclaiming the memory.

All in good time though! Reading this book will help you see that we need not sacrifice algorithmic performance while avoiding in-place mutation!