pure-fun / README.okasaki

This directory contains the Standard ML source code from

    Purely Functional Data Structures
    Chris Okasaki
    Cambridge University Press, 1998

The code is organized into files according to chapter, from "chp2.sml" to
"chp11.sml".  Each file is self-contained, except for a few miscellaneous
definitions in "base.sml".

The code in the book assumes two non-standard language extensions: support for
lazy evaluation and support for polymorphic recursion.  I have modified the
on-line code to work around the lack of polymorphic recursion, but I have
made only minor changes regarding lazy evaluation.  IN PARTICULAR, IF YOU
COMPILE THE CODE "AS IS", IT WILL NOT USE LAZY EVALUATION, AND SO WILL NOT
ACHIEVE THE RUNNING TIMES CLAIMED IN THE BOOK.

In the book, I assumed that lazy evaluation was supported in the language with
a $ operator: "$ exp" would create a suspension for the expression "exp", and
matching that suspension against a pattern of the form "$ pat" would evaluate
and memoize the suspension.  In the on-line code, I simulate this with the
following definition in "base.sml":

  datatype 'a susp = $ of 'a

But, of course, this $ constructor is not lazy!  

There are two further differences related to lazy evaluation.  First, the 
code in the book assumes that $ parses with a lower precedence than an ordinary
constructor.  Therefore, in the on-line code, I have replaced some occurrences
of "$ exp" with "$ (exp)".  Second, the code in the book assumes the
ability to write lazy functions using a special "fun lazy" syntax.  In the
on-line code, I have eliminated dependence on this form.

Note that Standard ML of New Jersey now supports lazy evaluation using a 
similar, but not quite identical, syntax.  Updating the on-line code
to use their syntax requires the following changes:

  - replace each occurrence of
        val s = $ (exp)
    with
        val lazy s = $ (exp)

  - replace each remaining occurrence of
        ... $ (exp) ...
    with
        let val lazy s = $ (exp)
        in ... s ... end


Chris Okasaki
cdo@cs.columbia.edu
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.