Purely Functional Data Structures for the Impure
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


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

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

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