Catenable Lists in SML

Companion source code to

Chris Okasaki
Amortization, Lazy Evaluation, and Persistence:
Lists with Catenation via Lazy Linking
FOCS'95, pages 646-654.

All companion source code is written for SML/NJ (version 0.93).

We give two implementations of catenable lists. The first (click here) is a more-or-less direct transcription of the psuedocode presented in the paper. The second (click here) is written in a more functional style.

These implementations of catenable lists depend on three further modules: delayed computations, streams (i.e. lazy lists), and queues.