From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA15507 for caml-redistribution; Sun, 10 Oct 1999 23:31:16 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA17305 for ; Sun, 10 Oct 1999 23:16:05 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id XAA15784; Sun, 10 Oct 1999 23:16:03 +0200 (MET DST) Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA13841; Sun, 10 Oct 1999 23:16:03 +0200 (MET DST) From: Pierre Weis Message-Id: <199910102116.XAA13841@pauillac.inria.fr> Subject: Re: Data structures in ocaml To: quercia@cal.enst.fr Date: Sun, 10 Oct 1999 23:16:02 +0200 (MET DST) Cc: caml-list@inria.fr In-Reply-To: <99101014230201.15999@Montchapet> from "Michel Quercia" at Oct 10, 99 12:56:15 pm X-Mailer: ELM [version 2.4 PL24 ME8] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: weis > : 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, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/