Chapter 1, Why Functional Programming?, takes you on a whirlwind tour of the functional programming (FP) paradigm. We try to highlight the many advantages FP brings to the table when compared with the imperative programming paradigm. We discuss FP’s higher level of abstraction, being declarative, and reduced boilerplate. We talk about the problem of reasoning about the state change. We see how being immutable helps realize "an easier to reason about system".

Chapter 2, Building Blocks, provides a whirlwind tour of basic concepts in algorithms. We talk about the Big O notation for measuring algorithm efficiency. We discuss the space time trade-off apparent in many algorithms. We next look at referential transparency, a functional programming concept. We will also introduce you to the notion of persistent data structures.

Chapter 3, Lists, looks at how lists are implemented in a functional setting. We discuss the concept of persistent data structures in depth here, showing how efficient functional algorithms try to minimize copying and maximize structural sharing.

Chapter 4, Binary Trees, discusses binary trees. We look at the traditional binary tree algorithms, and then look at Binary Search Trees.

Chapter 5, More List Algorithms, shows how the prepend operation of lists is at the heart of many algorithms. Using lists to represent binary numbers helps us see what lists are good at. We also look at greedy and backtracking algorithms, with lists at the heart.

Chapter 6, Graph Algorithms, looks at some common graph algorithms. We look at graph traversal and topological sorting, an important algorithm for ordering dependencies.

Chapter 7, Random Access Lists, looks at how we could exploit Binary Search Trees to access a random list element faster.

Chapter 8, Queues, looks at First In First Out (FIFO) queues. This is another fundamental data structure. We look at some innovative uses of lists to implement queues.

Chapter 9, Streams, Laziness, and Algorithms, looks at lazy evaluation, another FP feature. This is an important building block for upcoming algorithms, so we refresh ourselves with some deferred evaluation concepts.

Chapter 10, Being Lazy – Queues and Deques, looks at double-ended queues, which allow insertion and deletion at both ends. We first look at the concept of amortization. We use lazy lists to improve the queue implementation presented earlier, in amortized constant time. We implement deques also using similar techniques.

Chapter 11, Red-Black Trees, shows how balancing helps avoid degenerate Binary Search Trees. This is a comparatively complex data structure, so we discuss each algorithm in detail.

Chapter 12, Binomial Heaps, covers heap implementation offering very efficient merge operation. We implement this data structure in a functional setting.

Chapter 13, Sorting, talks about typical functional sorting algorithms. 

You need to install Scala and Clojure. All the examples were tested with Scala version 2.11.7.  The Clojure examples were tested with Clojure version 1.6.0. You don’t need any IDE as most of the examples are small enough, so you can key them in the REPL (Read/Eval/Print Loop).

You also need a text editor. Use whichever you are comfortable with.

The book assumes some familiarity with basic data structures. You should have played with fundamental data structures like linked lists, heaps, and binary trees. It also assumes that you have written some code in a functional language.

Scala is used as an implementation language. We do highlight related Clojure features too. The idea is to illustrate the basic design principles.

We explain the language concepts as needed. However, we just explain the basics and give helpful pointers, so you can learn more by reading the reference links.

We try to site links that offer hands-on code snippets, so you can practice them yourself.

Walking through an algorithm and discussing the implementation line by line is an effective aid to understanding.

A lot of thought has gone into making helpful diagrams. Quizzes and exercises are included, so you can apply what you've learned.

All the code is available online. We strongly advocate keying in the code snippets though, to internalize the principles and techniques.

Welcome to the wonderland of functional data structures and algorithms!

In this book, you will find a number of text styles that distinguish between different kinds of information. Here are some examples of these styles and an explanation of their meaning.

Code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles are shown as follows: "The following function f has a side effect, though."

A block of code is set as follows:

user=> (def v [7 11 19 52 42 72]) 
#'user/v 
user=> (def v1 (conj v 52)) 
#'user/v1 

If there is a line (or lines) of code that needs to be highlighted, it is set as follows:

scala> def pop(queue: Fifo): (Int, Fifo) = { 
     |   queue.out match { 
     |     case Nil => throw new IllegalArgumentException("Empty queue"); 
     |     case x :: Nil => (x, queue.copy(out = queue.in.reverse, Nil)) 
     |     case y :: ys => (y, queue.copy(out = ys)) 
     |   } 
     | } 
pop: (queue: Fifo)(Int, Fifo)

New terms and important words are shown in bold. Words that you see on the screen, for example, in menus or dialog boxes, appear in the text like this: "Clicking the Next button moves you to the next screen."

Feedback from our readers is always welcome. Let us know what you think about this book—what you liked or disliked. Reader feedback is important for us as it helps us develop titles that you will really get the most out of.

To send us general feedback, simply e-mail [email protected], and mention the book's title in the subject of your message.

If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, see our author guide at www.packtpub.com/authors.

Now that you are the proud owner of a Packt book, we have a number of things to help you to get the most from your purchase.