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
[Caml-list] Suggestion about balanced trees in stdlib
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Stefano Zacchiroli <zack@c...>
Subject: Re: [Caml-list] Suggestion about balanced trees in stdlib
On Sat, May 11, 2002 at 05:47:04PM +0200, Gerd Stolpmann wrote:
> type 'a map = Empty | Node of 'a map * key * 'a * 'a map * int
> type set = Empty | Node of set * elt * set * int
> The difference is that every map node has 6 words, and every set node
> consists of 5 words. My suggestion is to prefer the map representation,
> and define set = unit map, wasting one word per node, and making sets
> 20% larger.

Ok, I agree that this is the "clean" way to the goal.

Anyway I think that memory consumption is crucial for the standard
library, this is why I'm proposing a dirty trick for the set/map matter.
Usually I dislike tricks and prefer clean programming, but IMHO a
standard library is somewhat a particular case.


Why not use a single source file that implement both set and map using
some campl4 tricks like pa_ifdef module?
You may have two different definitions of tree and a pool of accessor
functions working on a tree and returning single components (hoping that
the compiler inline this kind of functions).
In the set case you doesn't need to use the value component of a tree
so you can avoid to compile the relative accessor function (poor gain)
and you can also compile a tree tuple without a value component.


[ Question: gurus, do you thinks this is a feasible solution or I'm
missing something? ]

I know, this is a really dirty trick. Also I don't know if is applicable
because I have never looked at the implementations and but
just as an idea it can work.

- reduce memory consumption for Set
- no code duplication

- objects (.cm{a,o,x...}) duplication
- really dirty!
- last time I looked at it camlp4 pa_ifdef module doesn't permit
  multiple declaration using only one "if" construct so you incurs in
  situations like:
     ifdef FOO then let bar = ...
     ifdef FOO then let quux = ...
     ifdef FOO then let baz = ...

Just a [dirty] idea.

Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy | ICQ# 33538863 |
"I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!" -- G.Romney
To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: