Re: Data structures in ocaml

From: Pierre Weis (
Date: Sun Oct 10 1999 - 23:16:02 MET DST

From: Pierre Weis <>
Message-Id: <>
Subject: Re: Data structures in ocaml
Date: Sun, 10 Oct 1999 23:16:02 +0200 (MET DST)
In-Reply-To: <99101014230201.15999@Montchapet> from "Michel Quercia" at Oct 10, 99 12:56:15 pm

> : any of the first functional constructor C of ty with (any : ty) as
> : argument. (Hence (any : string list) was [].)

> What about : "type t = T of int*t" (immutable circular int lists) ?
> Well there is a solution : "let rec dummy = T(0,dummy)" but in more
> complicated recursive type definitions the compiler will have to
> work hard to produce some plausible value, it seems to me that this
> should always be possible, am I right ?

This is always possible, and this was done properly via mutually
recursive definition of identifiers (let rec t0 = T (0, t0) in the
case of type t for instance). The real problems arrive when any is
encapsulated into polymorphic functions (for instance, ``any'' cannot
help to initialize a ``statically polymorphic'' array, that is an array
whose elements are statically completely unknown...). Then you must
extend the type-system with ``generic polymorphism'' to get types at
run-time (see the article "Extensional polymorphism" by Catherine
Dubois Francois Rouaix and Pierre Weis, POPL'95).

> Concerning varying arrays,
> --------------------------
> I had an idea not far from Markus Mottl's own.
> Define a new tag, let's call it Vtag flagging varying size (that is
> both growing and shrinking) objects. A Vobject would say :
> to erase pointers when shrinking a Varray ... Nice, but I have some
> doubts about O'caml implementors accepting my proposal.

Nice and simple enough anyway. Worth a try, if we are sure that ``growing
and shrinking objects'' are indeed reasonably general to be worth the
implementation effort (ask mister GC for a new tag, ask mister GC for
an addition to the mark and copy phases, decrement the maximum number
of constructors in sum types)...

> Concerning Lists implemented by varying arrays,
> -----------------------------------------------
> An awfull question pops up inside of me, how can one implement :
> let l1 = a :: l and l2 = b :: l
> if lists are actually arrays (with head at the end) without copying l ?

This question is difficult, I don't know how to obtain the same
sharing as usual lists as soon as vectors are used. For instance, I
don't know how to have a cons in constant time, since the vector may
overflow, that means that you have to extend it and copy all the
elements of the ``list'' in the fresh vector. Furthermore, if your
lists share sub lists it becomes extremely difficult not to keep some
pointer to the old vector, thus genrating lots of memory leaks.

More generally, concerning the lists John Skaller tries to implement,
we cannot really understand his problems as soon as we don't know what
is the complexity he needs for all the basic functions on his lists:

For O'Caml we have:
hd : O(1), tl : O(1), cons : O(1), nth l n : O(n)
append l1 l2 : O(len (l1))
append_lists [l1; l2; ... ln] : O(len (l1) + len (l2) + ... + len (ln-1))

What are the figures for Python lists ?
Are there other significant function for the list package ?

Pierre Weis

INRIA, Projet Cristal,,

This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:26 MET