Learning Functional Data Structures and Algorithms

Table of Contents

Learning Functional Data Structures and Algorithms

Credits

About the Authors

About the Reviewer

www.PacktPub.com

Why subscribe?

Customer Feedback

Preface

What this book covers 

What you need for this book 

Who this book is for 

Conventions 

Reader feedback

Customer support

Downloading the example code

Downloading the color images of this book

Errata

Piracy

Questions

1. Why Functional Programming?

The imperative way

Higher level of abstraction

Functional programming is declarative

No boilerplate

Higher order functions

Eschewing null checks

Controlling state changes

Recursion aids immutability

Copy-on-write

Laziness and deferred execution

Composing functions

Summary

2. Building Blocks

The Big O notation

Space/time trade-off

A word frequency counter

Matching string subsets

Referential transparency

Vectors versus lists

Updating an element

Not enough nodes

Complexities and collections

The sliding window

Maps

Persistent stacks

Persistent FIFO queues

Sets

Sorted set

Summary

3. Lists

First steps

List head and tail

Drop elements

Concatenating lists

Persistent data structures

Tail call optimization

List append

List prepend

Getting value at index

Modifying a list value

Summary

4. Binary Trees

Node definitions

Building the tree

Size and depth

Complete binary trees

Comparing trees

Flipping a binary tree

Binary tree traversal

The accumulator idiom

Binary Search Trees

Node insertion

Searching a key

Updating a value

Exercising it

Summary

5. More List Algorithms

Binary numbers

Addition

Multiplication

Greedy algorithms and backtracking

An example of a greedy algorithm

The backtracking jig

Summary

6. Graph Algorithms

Reversing a list

Graph algorithms

Graph traversal

Avoiding list appending

Topological sorting

Cycle detection

Printing the cycle

Summary

7. Random Access Lists

Incrementing a binary number

Adding two binary numbers

List of tree roots

Insertion

Lookup

Removal, head, and tail

Update

Summary

8. Queues

Understanding FIFO queues

Functional FIFO queues

Invariants

Implementing a priority queue

Understanding priority queues/heaps

Leftist trees

Functional heaps

Summary

9. Streams, Laziness, and Algorithms

Program evaluation

Eager evaluation

Argument evaluation

Lazy evaluation

Lazy evaluation in Scala

Lazy evaluation in Clojure

Memoization - remembering past results

Memoization in Scala

Memoization in Clojure

Memoizing simpleFactFun

Streams

Stream in Scala

Indexing the elements of a stream

Creation of an infinite length stream

Stream is immutable

Creating a stream from another

Stream to list

Appending one stream to another

Length of a stream

Some mathematical functions of the stream class

Some more methods of the stream class

Streams (lazy sequence) in Clojure

Creating a memoized function of lazy sequences in Clojure

Some algorithms on stream

Arithmetic progression

Arithmetic progression in Scala

Arithmetic progression in Clojure

Standard Brownian motion

Standard Brownian motion in Scala

Standard Brownian motion in Clojure

Fibonacci series

First form of Fibonacci series

Second form of Fibonacci series

Fibonacci series in Scala

Fibonacci series in Clojure

Summary

10. Being Lazy - Queues and Deques

Imperative implementations

Amortization

Problem with queues

Strict versus lazy

Streams

Streams meet queues

A sense of balance

Amortized deques

Summary

11. Red-Black Trees

Terminology

Almost balanced trees

The concept of rotation

Red-Black trees

Inserting a node

The Black-Red-Red path

Left, left - red child and grand child

Left child, right grand child

Right child, right grand child

Right, left

Verifying the transformation

Complexity

Summary

12. Binomial Heaps

Binomial trees

Left child, right sibling

A binomial heap

Linking up

Inserting a value

Binary number equivalence

Merging

Find the minimum

Deleting the minimum

Exercising the code

Complexity

Summary

13. Sorting

Stable and unstable sorting

Stable sorting

Unstable sorting

Bubble sort

Scala implementation of bubble sort

Complexity of bubble sort

Selection sort

Complexity of selection sort

Insertion sort

Complexity of insertion sort

Merge sort

Splitting the sequence

Merging two sorted subsequences

Complexity of merge sort

Quick sort

Partition

Complexity of quick sort

Summary

Learning Functional Data Structures and Algorithms

Learning Functional Data Structures and Algorithms

Copyright © 2017 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the authors, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

First published: February 2017

Production reference: 1170217

Published by Packt Publishing Ltd.

Livery Place

35 Livery Street

Birmingham B3 2PB, UK.

ISBN 978-1-78588-873-1

www.packtpub.com

Credits

About the Authors

Atul S. Khot grew up in Marathwada, a region of the state of Maharashtra, India. A self-taught programmer, he started writing software in C and C++. A Linux aficionado and a command-line guy at heart, Atul has always been a polyglot programmer. Having extensively programmed in Java and dabbled in multiple languages, these days, he is increasingly getting hooked on Scala, Clojure, and Erlang. Atul is a frequent speaker at software conferences, and a past Dr. Dobb's product award judge. In his spare time, he loves to read classic British detective fiction. He is a foodie at heart and a pretty good cook. Atul someday dreams of working as a master chef, serving people with lip-smacking dishes.

He was the author of Scala Functional Programming Patterns published by Packt Publishing in December 2015. The book looks at traditional object-oriented design patterns and shows how we could use Scala's functional features instead.

I would like to thank my mother, late Sushila S. Khot, for teaching me the value of sharing. Aai, I remember all you did for the needy girl students! Your support for the blind school - you brought hope to so many lives!  You are no more, however your kindness and selfless spirit lives on! I know you are watching dear mother, and I will carry on the flame till I live! I also would like to thank my father, late Shriniwas V. Khot. Anna, I have a photo of the 'Tamra pat'--an engraved copper plaque--commemorating your great contribution to the country's freedom struggle. You never compromised on core values --always stood for the needy and poor. You live on in my memories--a hero forever! I would also want to thank Martin Odersky for giving us the Scala programming language. I am deeply thankful to Rich Hickey and the Clojure community for their work on persistent data structures. Chris Okasaki’s Purely Functional Data Structures is a perennial source of inspiration and insight. I wish to thank Chris for writing the book. This book is influenced by many ideas Chris presented in his book. I also wish to thank the functional programming community for all the technical writings which is a source of continual learning and inspiration. I would love to express my heartfelt thanks to Nikhil Borkar for all the support through out the book writing. I also would take this opportunity to thank Hussain Kanchwala for the detailed editing efforts to make the book perfect. You guys are awesome! Thanks to y’all!

Raju Kumar Mishra is a consultant and corporate trainer for big data and programming. After completing his B.Tech from Indian Institute of Technology (ISM) Dhanbad, he worked for Tata Steel. His deep passion for mathematics, data science, and programming took him to Indian Institute of Science (IISc). After graduating from IISc in computational science, he worked for Oracle as a performance engineer and software developer. He is an Oracle-certified associate for Java 7.  He is a Hortonworks-certified Apache Hadoop Java developer, and holds a Developer Certification for Apache Spark (O'Reilly School of Technology and Databriks), and Revolution R Enterprise-certified Specialist Certifications. Apart from this, he has also cleared Financial Risk Manager (FRM I) exam. His interest in mathematics helped him in clearing the CT3 (Actuarial Science) exam.

My heartiest thanks to the Almighty. I would like to thank my mom, Smt. Savitri Mishra, my sisters, Mitan and Priya, and my maternal uncle, Shyam Bihari Pandey, for their support and encouragement. I am grateful to Anurag Pal Sehgal, Saurabh Gupta, and all my friends. Last but not least, thanks to Nikhil Borkar, Content Development Editor at Packt Publishing for his support in writing this book.

About the Reviewer

Muhammad Ali Ejaz is currently pursuing his graduate degree at Stony Brook University. His experience, leading up to this academic achievement, ranges from working as a developer to cofounding a start-up, from serving in outreach organizations to giving talks at various prestigious conferences. While working as a developer at ThoughtWorks, Ali cofounded a career empowerment based start-up by providing photographers a platform to showcase their art and be discovered by potential employers. His passion for computer science is reflected in his contributions to open source projects, such as GoCD, and his role in serving as the cofounder and Community Outreach Director of a non-profit organization, Women Who Code - Bangalore Chapter. Along with this, he has also been given the opportunity to speak at different conferences on Continuous Integration and Delivery practices.

When he is not coding, he enjoys traveling, reading, and tasting new cuisine. You can follow him on Twitter at @mdaliejaz.

I want to thank my Mom and Dad, who have always been my inspiration. I’d also like to thank Ahmad and Sana, my siblings, who have been a constant source of cheerful support. A lot of what I am today is because of them.

www.PacktPub.com

For support files and downloads related to your book, please visit www.PacktPub.com.

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at service@packtpub.com for more details.

At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters and receive exclusive discounts and offers on Packt books and eBooks.

https://www.packtpub.com/mapt

Get the most in-demand software skills with Mapt. Mapt gives you full access to all Packt books and video courses, as well as industry-leading tools to help you plan your personal development and advance your career.

Why subscribe?

Fully searchable across every book published by Packt

Copy and paste, print, and bookmark content

On demand and accessible via a web browser

Customer Feedback

Thank you for purchasing this Packt book. We take our commitment to improving our content and products to meet your needs seriously—that's why your feedback is so valuable. Whatever your feelings about your purchase, please consider leaving a review on this book's Amazon page. Not only will this help us, more importantly it will also help others in the community to make an informed decision about the resources that they invest in to learn. You can also review for us on a regular basis by joining our reviewers' club. If you're interested in joining, or would like to learn more about the benefits we offer, please contact us: customerreviews@packtpub.com.

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!

What this book covers 

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. 

What you need for this book 

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.

Who this book is for 

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