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

Question

可以使用let rec创建无限的循环列表，而不需要使用可变的引用：

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
;;

但是得到了以下错误

错误:这种表达式不允许作为“`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执行一些代码来动态地创建一个结构，它是无限的。恐怕您不能用cycle在OCaml中编写类似的函数。

如果您想在数据中引入一些循环，比如cycle in OCaml，那么您可以使用惰性结构来防止像Haskell的惰性列表那样的立即无限循环，或者使用变异通过替换来创建一个循环。OCaml的列表既不懒惰也不可变，因此不能编写动态构造环列表的函数。

Answer 2

如果您不介意使用黑魔法，您可以尝试以下代码：

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模块是非常不鼓励的。另一方面，还有一些工业强项计划和图书馆(Coq，Jane Street's Core，包括电池)，这些程序和图书馆都使用这种被禁止的艺术。

Answer 3

摄影师的答案已经足够好了。我只想在这里补充几点。

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

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

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;...]。

然而，当然，它将失败，因为它的运行将是无休止的，并最终堆叠溢出。

那么，为什么let rec circle2 = 1::2::3::circle2会工作呢？

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

首先，circle2是一个值，它是一个列表。在OCaml获得这些信息之后，它可以为circle2创建一个静态地址，并使用列表的内存表示形式。

内存的实际值是1::2::3::circle2，它实际上是Node (1, Node (2, Node (3, circle2)))，即带有int 1的节点和带有int 2的节点的地址，以及带有int 3的节点的地址和circle2的地址。但我们已经知道圆周的地址了，对吧？所以OCaml只是把圆圈的地址放在那里。

一切都会好起来的。

此外，通过这个例子，我们还可以知道一个事实，对于这样定义的无限圆圈列表，实际上并不需要有限的内存。它不是生成一个真正的无限列表来消耗所有内存，相反，当一个循环结束时，它只是“返回”到列表的顶部。

然后让我们回到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

除了递归函数的定义之外，let rec绑定构造还支持某些非函数值的递归定义，例如 设rec name1 =1 :：name2和name2 =2 :：name1，将name1绑定到循环列表1:2:1:2:2：…，name2到循环列表2：：1:2:1:1：…非正式地，可接受的定义类由那些定义组成，其中定义的名称只出现在函数体内部或作为数据构造函数的参数。

如果使用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