Re: [Caml-list] About Obj (was Recursive lists)

[Alex Baretta <alex@baretta.com>]

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