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

[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: -- (:) From: Alex Baretta Subject: Re: [Caml-list] Recursive lists
```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

```