Re: [Caml-list] Recursive lists

[skaller <skaller@users.sourceforge.net>]

On Sat, 2004-10-09 at 03:19, Alex Baretta wrote:
> Of course, a separate Cyclic_list module could be defined to 
> access the cyclic-safe functions, but from an abstract point of view 
> such functions logically belong to List.

No they don't. List is an inductive data type,
and it is always finite. A data structure with
a cyclic pointer chain cannot represent a list.

A cyclic list is actually an instance of a 
coinductive data type, and this particular
one is called a stream.

In fact the List module is already *faulty*
because it supplies hd and tl, which are not
list operators at all -- they're the characteristic
functions of streams (just as Cons and Empty characterise
lists).

So there is actually a good argument for a Stream
module with hd and tl functions (and lazy map ..)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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