Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Re: Okasaki's "Purely Functional Data Structures" translated to
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 1999-01-24 (14:44)
From: Markus Mottl <mottl@m...>
Subject: Re: Okasaki's "Purely Functional Data Structures" translated to

> >   * 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.

I haven't read his paper, I just know his book - there is nothing about
the second possibility in it (maybe I have overlooked it).

Anyway, I have compared performance between the two (just for some
common operations). Your version was about 3% faster - not really much,
but I added it again to the repository and renamed the former version to
"sb_ralist2". This should satisfy both the speed-hungry and the advocats
of elegance...

By the way, chapter seven is now available, too. And I have made the
necessary changes so that "PhysicistsQueue" (chapter six) works.

As always:

Best regards,

Markus Mottl,,