On Sat, Oct 23, 2004 at 12:02:26AM +1000, skaller wrote:

> > type 'a 'b tree = Leaf of 'a | Node of 'b * 'a 'b tree * 'a 'b tree
> > 
> > Does a "unit unit tree" take up less space than a "int int tree"?
> 
> No, this isn't possible usually, because any polymorphic
> algorithm using this data structure expects a fixed
> layout in memory.
> 
> So in this case, a dummy value must exist.
> 
> This problem can't arise in Felix or C++, because
> they both use extensional polymorphism
> (compile time instantiation).
> 
> The only way this might work in Ocaml is if 
> the pointer to value was replaced by NULL,
> but that would require a NULL check, and slow
> down the algorithm for all types just to save
> some memory in degenerate cases.

The value of type 'unit' is kind of like a NULL.  It isn't a pointer, it is
an integer value.  A leaf of an (int, int) tree for the value (Leaf 42)
would look like (where each line is a word):

  +------+
  |header|
  +------+
  |85    |
  +------+

For an (unit, unit) tree, the value for (Leaf ()) would look like:

  +------+
  |header|
  +------+
  |1     |
  +------+

For a ((int, int), (int, int)) tree, the value will be a pointer to the
pair (Leaf (4, 5)) (which must be boxed):

          +------+
          |header|
          +------+
          |ptr   |---+
          +------+   |
                     |
    +----------------+
    |
    +-->  +------+
          |header|
          +------+
          |9     |
          +------+
          |11    |
          +------+

So, storing the unit type is the same efficiency as storing an int type,
both of which take less heap space than storing most other types.

Dave

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