How do I write a function to create a circular version of a list in OCaml?

Question

Its possible to create infinite, circular lists using let rec, without needing to resort to mutable references:

let rec xs = 1 :: 0 :: xs ;;

But can I use this same technique to write a function that receives a finite list and returns an infinite, circular version of it? I tried writing

let rec cycle xs = 
    let rec result = go xs and
            go = function
              | [] -> result
              | (y::ys) -> y :: go ys in
    result
;;

But got the following error

Error: This kind of expression is not allowed as right-hand side of `let rec'

Hame

This is not a problem of circularity. You cannot write an expression which may cause recursive computation in the rhs of let rec: see #19860453 – Infanticide

All the suggestions in that link you posted involve using a mutable reference (either directly or via lazy to tie the knot). Is it really impossible to rewrite cycle so it uses just letrec? – Hame

Related #19457914 – Sulamith

Answer 1

Your code has two problems:

• result = go xs is in illegal form for let rec
• The function tries to create a loop by some computation, which falls into an infinite loop causing stack overflow.

The above code is rejected by the compiler because you cannot write an expression which may cause recursive computation in the right-hand side of let rec (see Limitations of let rec in OCaml).

Even if you fix the issue you still have a problem: cycle does not finish the job:

let rec cycle xs =
  let rec go = function
    | [] -> go xs
    | y::ys -> y :: g ys
  in
  go xs;;

cycle [1;2];;

cycle [1;2] fails due to stack overflow.

In OCaml, let rec can define a looped structure only when its definition is "static" and does not perform any computation. let rec xs = 1 :: 0 :: xs is such an example: (::) is not a function but a constructor, which purely constructs the data structure. On the other hand, cycle performs some code execution to dynamically create a structure and it is infinite. I am afraid that you cannot write a function like cycle in OCaml.

If you want to introduce some loops in data like cycle in OCaml, what you can do is using lazy structure to prevent immediate infinite loops like Haskell's lazy list, or use mutation to make a loop by a substitution. OCaml's list is not lazy nor mutable, therefore you cannot write a function dynamically constructs looped lists.

Infanticide

Answer 2

If you do not mind using black magic, you could try this code:

let cycle l =
  if l = [] then invalid_arg "cycle" else
  let l' = List.map (fun x -> x) l in   (* copy the list *)
  let rec aux = function
    | [] -> assert false
    | [_] as lst ->   (* find the last cons cell *)
        (* and set the last pointer to the beginning of the list *)
        Obj.set_field (Obj.repr lst) 1 (Obj.repr l')
    | _::t -> aux t
  in aux l'; l'

Please be aware that using the Obj module is highly discouraged. On the other hand, there are industrial-strength programs and libraries (Coq, Jane Street's Core, Batteries included) that are known to use this sort of forbidden art.

Begun

Answer 3

camlspotter's answer is good enough already. I just want to add several more points here.

First of all, for the problem of write a function that receives a finite list and returns an infinite, circular version of it, it can be done in code / implementation level, just if you really use the function, it will have stackoverflow problem and will never return.

A simple version of what you were trying to do is like this:

let rec circle1 xs = List.rev_append (List.rev xs) (circle1 xs)
val circle: 'a list -> 'a list = <fun>

It can be compiled and theoretically it is correct. On [1;2;3], it is supposed to generate [1;2;3;1;2;3;1;2;3;1;2;3;...].

However, of course, it will fail because its run will be endless and eventually stackoverflow.

---

So why let rec circle2 = 1::2::3::circle2 will work?

Let's see what will happen if you do it.

First, circle2 is a value and it is a list. After OCaml get this info, it can create a static address for circle2 with memory representation of list.

The memory's real value is 1::2::3::circle2, which actually is Node (1, Node (2, Node (3, circle2))), i.e., A Node with int 1 and address of a Node with int 2 and address of a Node with int 3 and address of circle2. But we already know circle2's address, right? So OCaml just put circle2's address there.

Everything will work.

Also, through this example, we can also know a fact that for a infinite circled list defined like this actually doesn't cost limited memory. It is not generating a real infinite list to consume all memory, instead, when a circle finishes, it just jumps "back" to the head of the list.

---

Let's then go back to example of circle1. Circle1 is a function, yes, it has an address, but we do not need or want it. What we want is the address of the function application circle1 xs. It is not like circle2, it is a function application which means we need to compute something to get the address. So,

OCaml will do List.rev xs, then try to get address circle1 xs, then repeat, repeat.

---

Ok, then why we sometimes get Error: This kind of expression is not allowed as right-hand side of 'let rec'?

From http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#s%3aletrecvalues

the let rec binding construct, in addition to the definition of recursive functions, also supports a certain class of recursive definitions of non-functional values, such as

let rec name1 = 1 :: name2 and name2 = 2 :: name1 in expr which binds name1 to the cyclic list 1::2::1::2::…, and name2 to the cyclic list 2::1::2::1::…Informally, the class of accepted definitions consists of those definitions where the defined names occur only inside function bodies or as argument to a data constructor.

If you use let rec to define a binding, say let rec name. This name can be only in either a function body or a data constructor.

In previous two examples, circle1 is in a function body (let rec circle1 = fun xs -> ...) and circle2 is in a data constructor.

If you do let rec circle = circle, it will give error as circle is not in the two allowed cases. let rec x = let y = x in y won't do either, because again, x not in constructor or function.

---

Here is also a clear explanation:

https://realworldocaml.org/v1/en/html/imperative-programming-1.html

Section Limitations of let rec

Gravesend