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'

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.

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.