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

[Caml-list] Recursive lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-10-13 (11:41) From: Alex Baretta Subject: Re: [Caml-list] About Obj (was Recursive lists)
```james woodyatt wrote:
me-now-or-pay-me-later sort of game you're playing here.
>
> Rather than whack on the immutable list, maybe you should consider doing
> this:
>
>     type 'a mlist = N | C of 'a mcell
>     and 'a mcell = { mutable cdr: 'a; mutable car: 'a mlist }
>
> No need to thank me.

This point of view is simply wrong. We use immutable lists, which can be
infinite. This data structure, or I should say this module interface,
perfectly models our program's needs. However, as I discussed with
Xavier, we must guarantee that the algorithm which scans this list will,
at some point terminate, whether the list is finite or not. This can be
done because cycle detection is decidable and it's complexity in
realistic scenarios (ours, as far as I'm concerned) is O(1), the
constant complexity being achieved through the tail-stacking algorithm
which only stacks a small number of nodes, number which is indipendent
of the problem size.

The need for a List (or Cyclic_list) module encapsulating the
abstraction of a cyclic list emerges when we try to build an input
data-structure to feed our algorithm. The use of Obj within a specific
module is perfectly acceptable so long as it is needed to implement
functionality which cannot be achieved in the core language. The example
of the tail recursive implementation of List.map is pertinent, and shows
the point.

You might have noticed that Caml breeders use Obj fairly liberally when
it is needed to achieve a higher of abstraction which cannot be modeled
in the core language.

Alex

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

```