如何编写一个函数来在OCaml中创建一个循环版本的列表？

Question

它可以创建使用无限的，圆形的名单让拍摄，而无需诉诸可变引用：

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

但我可以使用同样的技术来存储接收有限的列表，并返回一个无限的功能，它的圆形版本？我试着写

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

但有以下错误

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

Answer 1

您的代码有两个问题：

• result = go xs以非法形式let rec
• 函数试图创建循环通过一些计算，陷入无限循环导致堆栈溢出。

上面的代码由编译器拒绝，因为也可以不写其可以以let rec右手侧引起递归运算（见Limitations of let rec in OCaml）的表达式。

即使你解决这个问题，你仍然有一个问题：cycle不完成作业：

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

cycle [1;2];; 

cycle [1;2]失败，因为堆栈溢出。

在OCaml中，let rec只有当它的定义是“静态”并且不执行任何计算时才能定义循环结构。 let rec xs = 1 :: 0 :: xs就是这样一个例子：(::)不是一个函数，而是一个纯粹构造数据结构的构造函数。另一方面，cycle执行一些代码执行动态地创建一个结构，它是无限的。我担心你不能在OCaml中写入像cycle这样的函数。

如果你想在OCaml中引入一些像cycle这样的数据循环，你可以做的就是使用lazy结构来防止像Haskell懒惰列表这样的直接无限循环，或者使用变异来通过替换来创建循环。 OCaml的列表不是懒惰也不可变的，因此你不能动态地写一个函数来构造循环列表。

Answer 2

camlspotter的答案已经足够好了。我只想在这里添加更多点。

首先，对于write a function that receives a finite list and returns an infinite, circular version of it的问题，它可以在代码/实现级别完成，只要你真的使用该函数，它将有stackoverflow的问题，并永远不会返回。

的是你所试图做一个简单的版本是这样的：

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

可以编译和理论是正确的。在[1;2;3]上，它应该生成[1;2;3;1;2;3;1;2;3;1;2;3;...]。

但是，当然，它会失败，因为它的运行将是无止境的，并最终stackoverflow。

---

那么为什么let rec circle2 = 1::2::3::circle2将工作？

让我们看看如果你这样做会发生什么。

首先，circle2是一个值，它是一个列表。在OCaml获得此信息后，它可以为列表2的存储器表示形式创建一个静态地址。

存储器的实际值为1::2::3::circle2，实际值为Node (1, Node (2, Node (3, circle2)))，即A节点为int 1，节点地址为int 2，节点地址为int 3，地址为circle2。但我们已经知道circle2的地址了，对吧？所以OCaml只是把circle2的地址放在那里。

一切都会奏效。

另外，通过这个例子，我们也可以知道这样一个事实，即对于这样定义的无限循环列表实际上并不会限制内存的成本。它不会生成一个真正的无限列表来消耗所有的内存，相反，当一个圆圈结束时，它会跳回到列表头部。

---

让我们回到circle1的例子。 Circle1是一个函数，是的，它有一个地址，但我们不需要或不需要它。我们想要的是功能应用circle1 xs的地址。它不像circle2，它是一个函数应用程序，这意味着我们需要计算一些东西来获取地址。所以，

OCaml将做List.rev xs，然后尝试获得地址circle1 xs，然后重复，重复。

---

好的，那么为什么我们有时会得到Error: This kind of expression is not allowed as right-hand side of 'let rec'？

从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.

如果使用let rec定义绑定，说let rec name。此name只能在函数体或数据构造函数中使用。

在前面的两个示例中，circle1位于函数体（let rec circle1 = fun xs -> ...）中，而circle2位于数据构造函数中。

如果你做let rec circle = circle，它会给出错误，因为圆不在两个允许的情况下。 let rec x = let y = x in y也不会这样做，因为再次，x不在构造函数或函数中。

---

这里也是一个明确的交代：

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

科Limitations of let rec

Answer 3

如果你不介意使用黑魔法，你可以试试这个代码：

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' 

请注意，使用Obj模块非常重要iscouraged。另一方面，已知有使用这种禁止艺术的工业强项目和图书馆（Coq，简街的核心，电池包括在内）。