From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA07734 for caml-redistribution; Sun, 24 Jan 1999 15:44:53 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA04492 for ; Sat, 23 Jan 1999 18:56:28 +0100 (MET) Received: from miss.wu-wien.ac.at (miss.wu-wien.ac.at [137.208.107.17]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id SAA20851 for ; Sat, 23 Jan 1999 18:56:20 +0100 (MET) Received: (from mottl@localhost) by miss.wu-wien.ac.at (8.9.0/8.9.0) id SAA28937; Sat, 23 Jan 1999 18:56:10 +0100 (MET) From: Markus Mottl Message-Id: <199901231756.SAA28937@miss.wu-wien.ac.at> Subject: Re: Okasaki's "Purely Functional Data Structures" translated to To: bernardp@cli.di.unipi.it (Pierpaolo Bernardi) Date: Sat, 23 Jan 1999 18:56:10 +0100 (MET) Cc: caml-list@inria.fr (OCAML) In-Reply-To: from "Pierpaolo Bernardi" at Jan 22, 99 12:34:00 pm X-Mailer: ELM [version 2.4 PL21] MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Sender: weis Hello, > > * 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: http://miss.wu-wien.ac.at/~mottl/ocaml_sources/intro.html Best regards, Markus -- Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl