Re: [Caml-list] Recursive lists

[Alex Baretta <alex@baretta.com>]

Keith Wansbrough wrote:
> 
> How could they do this?  It's just a list; there's nothing special
> about it, except that it has no end.

Lists can be recursive. This means that the list type models a set of 
values which includes the cyclic lists. The ocaml type system allow both 
for such values and for functions manipulating them, so it's perfectly 
natural to expect the List module to treat cyclic lists correctly. 
Besides, the cyclicity of a list is a perfectly decidable property by 
virtue of the pumping lemma.

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

Good point; however, we must keep a list of tails of visited nodes. 
Physical equality of nodes is a necessary but insufficient condition for 
recursiveness. On the other hand, if two nodes of the list have the same 
tail, then we have proven that the list is cyclic.

> But it would be better to design a more appropriate 
> data structure for your application, one for which such tricks are not 
> needed.

There is no more appropriate data structure than a cyclic list to model 
a possibily infinite (cyclic) sequence of input data. Have you ever seen 
type schemas like the following:
# type 'a t = 'a -> 'a t;;
type 'a t = 'a -> 'a t
This is a perfectly sensible use of recursive data structures: there is 
no other way to model a type whose expanded representation is infinite.
type 'a t = 'a -> 'a -> 'a -> ...

> What are you trying to do?

We are modelling an optimization problem where a finite number of 
requests must be served, as efficiently as possible, from a possibly 
infinite set of instances of a finite number of classes of resources. 
Each resource class is modelled by a list element. The cyclicity of the 
resource list can be used to express no limits on the amount of 
resources available. Yet, the optimization program must know better than 
simply scan the list sequentially, or unsatisfiable constraint sets 
cannot be identified in finite time.

Our algorithm works now, so we do not depend on the availability of 
cyclic-list aware standard library. We are simply trying to point out 
that the current List module is very naif about infinite lists. I would 
like to start a discussion as to whether the List module ought to 
correctly handle cyclic lists or not. 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.

Alex

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