[Caml-list] Circuralizing lists

[Till Varoquaux]

Writing the list containing an inifinite number of ones can easily be done as:

let rec ones = 1::ones

I however don't know of any type safe to generate the infinite list
which is the repetition of a given list (in a type safe non lazy way).
What I'm looking for is a code that would do:

let circularize = function
| [] -> failwith "cannot circularize empty lists"
| l -> let rec res = l@res in res

Is this at all possible?

Cheers,
Till

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[Alain Frisch]

Till Varoquaux wrote:
> Writing the list containing an inifinite number of ones can easily be done as:
>
> let rec ones = 1::ones
>
> I however don't know of any type safe to generate the infinite list
> which is the repetition of a given list (in a type safe non lazy way).
> What I'm looking for is a code that would do:
>
> let circularize = function
> | [] -> failwith "cannot circularize empty lists"
> | l -> let rec res = l@res in res
>
> Is this at all possible?

No, this is not possible (using only safe features). The only recursive
(non functional) value loops that can be built have a fixed shape.

-- Alain

[Jon Harrop]

On Monday 26 November 2007 21:46, Till Varoquaux wrote:
> Writing the list containing an inifinite number of ones can easily be done
> as:
>
> let rec ones = 1::ones
>
> I however don't know of any type safe to generate the infinite list
> which is the repetition of a given list (in a type safe non lazy way).
> What I'm looking for is a code that would do:
>
> let circularize = function
>
> | [] -> failwith "cannot circularize empty lists"
> | l -> let rec res = l@res in res
>
> Is this at all possible?

OCaml only permits restricted static forms of this construct. The only
practical application of this restricted form that I am aware of is in
avoiding dummy values when creating simple cycles such as the environments of
recursive closures in an interpreter.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

[mgio...@gmail.com]

On Nov 26, 7:02 pm, Alain Frisch <al...@frisch.fr> wrote:
> Till Varoquaux wrote:
> > Writing the list containing an inifinite number of ones can easily be done as:
>

> > [...]

>
> > Is this at all possible?
>
> No, this is not possible (using only safe features). The only recursive
> (non functional) value loops that can be built have a fixed shape.

The operative word is, here, "safe". Suppose you have an unsafe
operation:

val rplacd : 'a list -> 'a list -> 'a list

that replaces the tail of the first list with the second, and returns
the original tail.
Then, we can thread circular lists easily:

let necklace = function
| [] -> invalid_arg "necklace"
| x :: _ as l ->
let p = ref l in
while (match !p with _ :: [] -> false | _ :: t -> p := t; true) do
() done;
ignore (rplacd !p l);
l

Simply find the last element in the list and close it back to the
beginning.
Rplacd can be written with help of the Obj module:

let rplacd : 'a list -> 'a list -> 'a list = fun l m ->
let o = Obj.repr l in
let t = Obj.field o 1 in
Obj.set_field o 1 (Obj.repr m);
Obj.obj t

and knowing that the layout of lists in memory is fixed (a tagged pair
of a value and a list).

[David Thomas]

This depends what you mean by "at all possible." With
the built in lists, the answers others have given are
correct - the short answer being "no." That said, if
it's exceedingly useful for your application, you
could do something like:

type 'a rlist = Empty | Cons of 'a * 'a rlist ref;;

let circularize l =
let l1 = ref Empty in
let l2 = List.fold_right (fun a b -> ref (Cons
(a, b))) l l1 in
l1 := !l2; l1;;

Most of what is in List is pretty trivial to duplicate
for the above type, and you could hide the mutability.
Of course, matching is no longer pretty... but "at
all possible"? Yes.

____________________________________________________________________________________
Looking for last minute shopping deals?
Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping