Re: [Caml-list] Recursive lists

[Jon Harrop <jon@jdh30.plus.com>]

On Friday 08 October 2004 15:44, Alex Baretta wrote:
> Lazy lists or streams are not good enough in the general scenario. We 
> don't need to exhaustively explore the cyclic data structures.

Yes.

> The 
> properties we are interested in can be proven in finite time by
> analyzing the list structure with the physical equality operator.

No. I think you'll want "physical comparison operators" to do this 
efficiently, e.g. to build a set of visited nodes, otherwise you'll have to 
loop through all the possible ones giving you a search complexity of O(n) 
instead of O(ln n).

As "physical comparison operators" don't exist, I think you'd be better off 
using a directed cyclic graph with the notion of "physical" replaced with a 
notion of "index", so you number the nodes. Then you can build a set of 
visited nodes and search it to check for cyclic bits.

> I argue that since they are
> legimitate citizens of the language, the standard library should handle
> them correctly. We are willing to contribute our code, so that this
> might not weigh on the Caml breeders.

IMHO, this should certainly not go in the core library. These functions are 
much more specialised that the current code and are likely to be 
significantly slower. Perhaps the library documentation should state which 
functions assume a non-cyclic list.

Also, I'd be surprised if the required functionality didn't already exist in a 
graph library, although perhaps not specialized to one root and one edge out 
of each vertex.

Cheers,
Jon.

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