Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
[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-08 (23:30)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Recursive lists
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

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

John Skaller,
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: