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

[Caml-list] Polymorphism and the "for" loop
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: David Brown Subject: Re: [Caml-list] Polymorphism and the "for" loop
```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):

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

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

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

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

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

```