How do I write a function to create a circular version of a list in OCaml?
It is possible to create infinite circular lists using let rec, without having to resort to mutable references:
let rec xs = 1 :: 0 :: xs ;;
But can I use this same technique to write a function that takes a finite list and returns an infinite circular version? I have tried writing
let rec cycle xs =
let rec result = go xs and
go = function
| [] -> result
| (y::ys) -> y :: go ys in
result
;;
But I got the following error
Error: This kind of expression is not allowed as the right-hand side of `let rec '
source to share
There are two problems in your code:
-
result = go xs
is in illegal form forlet rec
- The function tries to create a loop through some computation, which ends up in an infinite loop causing a stack overflow.
The above code is rejected by the compiler because you cannot write an expression that can cause recursive evaluation on the right-hand side let rec
(see the limitations of let rec in OCaml ).
Even if you fix the problem, you still have a problem: cycle
does not execute the task:
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.
OCaml let rec
can only define a closed structure when its definition is "static" and does not perform any computation. let rec xs = 1 :: 0 :: xs
- such an example: (::)
it is not a function, but a constructor that builds a data structure. On the other hand, it cycle
does some code execution to dynamically create structure and infinity. I am afraid that you cannot write a function like cycle
in OCaml.
If you want to introduce some loops on type data cycle
in OCaml, then you can use a lazy structure to prevent immediate infinite loops like Haskell's lazy list, or use mutation to create a loop by replacing. OCaml's list is not lazy or modified, so you can't write a function, it dynamically builds looped lists.
source to share
If you don't mind using black magic, you can 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'
Remember that using the Obj module is highly discouraged. On the other hand, there are industrial programs and libraries (Coq, Jane Street Core, Batteries included) that are known to use this forbidden art.
source to share
Camlspotter's answer is already good enough. I just want to add a few more points.
First of all, for the problem write a function that receives a finite list and returns an infinite, circular version of it
, it can be done at the code / implementation level, it's just that if you actually use this function, it will have a stack thread problem and it will never return.
A simple version of what you were trying to do looks 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 correct. It is [1;2;3]
supposed to be created [1;2;3;1;2;3;1;2;3;1;2;3;...]
.
However, of course it won't work because it will run endlessly and eventually stackoverflow.
So why let rec circle2 = 1::2::3::circle2
would it work?
See what happens if you do.
First circle2
is the value, and this is the list. After OCaml receives this information, it can create a static address for circle2 with a memory representation from the list.
The real memory value 1::2::3::circle2
that is actually equal Node (1, Node (2, Node (3, circle2)))
, that is, A Node with int 1 and address a Node with int 2 and address a Node with int 3 and address of circle2. But we already know the address of circle2, don't we? So OCaml just posted the address circle2.
Everything will work.
Also, in this example, we can also know that there is actually no limited memory cost for an infinite circular list defined in this way. It doesn't generate a real infinite list to consume all memory, instead, when the circle ends, it just jumps back to the beginning of the list.
Now let's go back to the example circle1
. Circle1 is a function, yes, it has an address, but we don't need it or need it. We need the address of the function app circle1 xs
. This is not like circle2, it is a function app which means we need to compute something to get the address. So,
OCaml will execute List.rev xs
, then try to get the address circle1 xs
, then retry, retry.
Okay then why do 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 defining recursive functions, also supports a specific class of recursive defining non-functional values such as
let rec name1 = 1 :: name2 and name2 = 2 :: name1 in expr, which binds name1 to a looped list 1 :: 2 :: 1 :: 2 :: ... and name2 to a looped list 2 :: 1 :: 2 :: 1 :: ... Informally, the class of accepted definitions consists of those definitions where certain names appear only within functions or as an argument to a data constructor.
If you are using let rec
to define a binding, say let rec name
. This one name
can only be in the body of a function or a data constructor.
In the previous two examples, it circle1
is in the body of the function ( let rec circle1 = fun xs -> ...
), and circle2
in the data constructor.
If you do let rec circle = circle
it will give an error as the circle is not in the two allowed cases. let rec x = let y = x in y
it won't either, because again x is not in a constructor or function.
Here's also a clear explanation:
https://realworldocaml.org/v1/en/html/imperative-programming-1.html
Section Limitations of let rec
source to share