Re: [Caml-list] Suggestion about balanced trees in stdlib

[Stefano Zacchiroli <zack@cs.unibo.it>]

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.

<WARNING_dirty_trick>

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.

</WARNING_dirty_trick>

[ 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 set.ml and map.ml but
just as an idea it can work.

Pros:
- reduce memory consumption for Set
- no code duplication

Cons:
- 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.
Cheers.

-- 
Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy
zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro
"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 caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners