Re: Okasaki's "Purely Functional Data Structures" translated to

[Pierpaolo Bernardi <bernardp@cli.di.unipi.it>]

On Thu, 21 Jan 1999, Markus Mottl wrote:

> Although this implementation seems to be quite perfect, I have allowed
> myself to make some very small changes, so that it can be immediately
> used as a module and fits better to the way modules are implemented in
> the standard library.

Good.

> The following changes should be noted:

>   * The type of these lists is not "ralist" anymore in the module but
>     "t". This corresponds to the way this is handled in the standard
>     modules.

Rigth. 

>   * A somewhat bigger change: the type of the list is not:
> 
>       type 'a ralist = Nil | Root of int * 'a tree * 'a ralist
> 
>     but now:
> 
>       type 'a t    = (int * 'a tree) list
> 
>     I think that new users will understand details of implementation
>     easier with this change. It also comes closer to Okasaki's version.

Okasaki in his paper on RALs presents both versions.  The one I
used is faster for Ocaml, so I suggest that you use the version I sent.
Users should use the book or the paper to understand details.

>   * The rest of the changes concern mainly layout (hardly noticable).

De gustibus...  8-)

Cheers,
Pierpaolo