HTTPS clone URL
Subversion checkout URL
Purely functional datastructures
Fetching latest commit...
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
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@example.com