README-Okasaki.md

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 [email protected]