Re: [Caml-list] Recursive lists

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

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