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 (14:32)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Recursive lists
On Fri, 2004-10-08 at 23:31, Keith Wansbrough wrote:
> > Can some functions of the List library support the use of the recursive 
> > lists?

> How could they do this?  

> You might be able to do it by keeping a list of all the nodes you've 
> visited, and using physical equality to check if you have already 
> visited a node.

I use that technique to perform recursive descent
on acyclic graphs, which the recursive list is.

For a list with the cycle *known* to be length 1,
this is very cheap, since you only need to compare
against previous element.

You can also use lazy evaluation.

An example of a stream (infinite list) being a *correct* 
data structure is a list of tokens with a cycle on 
the 'end of file' token.

Much easier to analyse with matches against substring
patterns .. since you don't have to worry about
the end of the list.

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: