pure-fp-book

pure-fp-book copied to clipboard

Purely Functional Data Structures for the Impure

This is a working title. Other possibilities are: - Purely Functional Data Structures... a) ... for the Perl Programmer b) ... for the Working Programmer c) ... for the Mutable, Rank-Scented Many

a. was the original idea, but is perhaps a bit ghetto.  May be better to be
   a generic algorithms book, with appendices for each language?
b. steals 2 classic FP text titles for the price of 1!
c. is from Shakespeare, but perhaps a little rude ;-)

Intended Audience

Programmers using dynamic languages (Perl, Python, Ruby, Javascript), who are interested in functional programming

The most celebrated book on these is Chris Okasaki's celebrated "Purely Functional Data Structures", which, though very readable, is targeted towards the computer science academic with a background in functional programming. While the current book is not intended as a tutorial on functional programming from the ground up, it will work its way up to more complex structures, provide practical motivations and exercises where appropriate, and avoid mathematical terminology.

Reviewer Guidelines

I appreciate all suggestions and critiques, especially:

• is the work accurate?
• is the work complete?
• is the work coherent?
• are there missing sections and subjects?
• are the examples effective?
• is the flow of information appropriate?

Building this Book

Please read the INSTALL file in this distribution for more details

Contributing

This book will always be licensed under a Creative Commons license (see LICENSE)

Please feel free to fork this book on github, and submit pull requests (or bug reports) of suggestions and contributions.

Draft outline

1. Introduction

   • Why purely functional data-structures?
     • easier to reason about
     • higher-level features: Undo
     • concurrency
     • memory sharing
     • case study: Git
   • Survey of existing work (Okasaki, etc.)
   • Aim of book
     • to provide a grounding to Purely Functional data-structures
     • for the working programmer (not for CompSci audience)
     • with examples in Modern Perl

2. Lists

   • A mutable list: Perl's array (a Vector type)

     • advantages
     • disadvantages

   • Singly-linked lists

     • Mutable versus Immutable
     • code

   • List operations

     • map / fmap
     • filter

   • Interlude: Tail recursion, TCE

   • Doubly-linked lists?

     • mutable... immutable?
     • pointers
     • code
     • rewrite with Data::Zipper

   • Exercise: implement a turing machine with a zipper onto an infinite (in both directions) list

   • Show me the Code!: implementations of the above concepts in

     • Modern Perl with Moose
     • Javascript
     • Ruby
     • Python

3. Objects, Trees and Dictionaries

   • Immutable OO objects

     • updating child objects: the problem
     • Zipper!

   • Compare trees

   • Dictionaries

     • Mutable versus Immutable
     • Hash
     • Tree. Why?

   • Simple Binary tree

     • List to tree
     • Binary search
     • Interlude: explanation of O(log n)

   • Operations

     • map (fmap)
     • Data::Visitor

   • Balanced trees

     • When trees go wrong
     • Red black algorithm
     • Pattern matching
     • Insertion
     • Deletion

   • Zippers

   • Exercise: ???

   • Show me the code!

4. Strings

   • Mutable strings

   • Piece-table / rope

     • backed by singly-linked list
     • backed by red-black-tree
       • an Enfilade!
     • Zipper
     • fmap
     • search

   • Exercise: ???

   • Show me the code!

5. Grids

   (Not certain how to approach this yet!)

   • Mutable grids

     • Array of Arrays

   • How to do grids immutably?

     • List of lists?
     • Dictionary lookup of (x,y) coordinates
     • Quad-tree
     • intersecting Row/Column trees
     • Zippers?
       • may not be relevant here, as we don't have a linear, non-cyclic, inorder traversal

   • Exercise: ???

   • Show me the code!

6. Graphs

   • OO style mutable graph, modeled with nodes

     • how to implement as purely-functional...?
     • ... while retaining sharing

   • Adjacency matrix

     • algorithms

   • Exercise: ???

   • Show me the code!

7. Conclusion