Learning Functional Data Structures and Algorithms电子书

Learning Functional Data Structures and Algorithms

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