These files contain an SML-to-OCaml translation of source examples taken from the following book:
Purely Functional Data Structures Chris Okasaki Cambridge University Press, 1998 Copyright (c) 1998 Cambridge University Press
Some short notes regarding my port:
I have tried to stick as close as possible to the original code, but sometimes this cannot be done.
The first nine chapters are translated now. There are two further chapters, whose implementation requires polymorphic recursion. This feature was not available in OCaml for a while, which is why they have not been translated yet. Feel free to contribute them!
Notes on efficiency:
Because the data structures are purely functional, they profit a lot from garbage collector settings. In case you find that some of them are not efficient enough, you might want to raise the memory overhead parameter of the garbage collector. Performance is in general excellent.
The following rules / differences to the original sources exist:
- No base module
Since there is hardly anything indispensable in the base module, I copied the few relevant declarations into each module. This allows for easier testing, because the modules do not depend on others.
Names are created by the following rules:
Module types are written in capitals. If they consist of more than a word, an underscore ('_') is placed between the words.
Names of exceptions follow the same rule as modules types.
Module implementations have to start with a capital letter, the rest of the name is lowercase - except if it consists of more than one word. In this case the first letter of the following word is uppercase. There is no underscore between words.
Currying of function parameters
Currying is not used anywhere in the original source. I have tried to curry parameters where it makes sense. Tuples that represent a named type (e.g. some data structure) are not curried in functions that are hidden by a signature restriction. This seems to aid comprehension. Functions offered via the module interface (signature) do not reveal such implementation details (i.e. the concrete type) anyway.
- Superfluous bindings
If a parameter is never used in a following expression, it is not bound to any name. '_' will hold its place.
- Lazy evaluation
The syntax for lazy evaluation used to implement the datastructures and algorithms that require them is quite different from the original. The "lazy" type is used to specify datastructures that need lazy evaluation. Since recently, OCaml now also supports pattern matching on lazy values, which is used throughout.
To make the syntax at least a bit more similar to the original, I have also introduced the prefix operator '!$', which stands for 'force" - it forces evaluation of a lazy expression. To make an expression lazy, the expression 'lazy' is used.
There is a test function at the end of the translation of chapter 4, the chapter in which lazy evaluation and streams (= lazy lists) are introduced. Uncomment it to see how lazy evaluation works.
Enjoy the data structures!
Rutherford, March 28, 2012 Markus Mottl (email@example.com)