6

它可以使用 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' 的右侧

4

3 回答 3

7

您的代码有两个问题：

  • result = go xs是非法的let rec
  • 该函数尝试通过一些计算创建一个循环，该循环陷入无限循环，导致堆栈溢出。

上面的代码被编译器拒绝，因为您不能在右侧编写可能导致递归计算的表达式let rec（请参阅OCaml 中 let rec 的限制）。

即使你解决了问题，你仍然有一个问题：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在 OCaml 中那样在数据中引入一些循环，你可以做的是使用惰性结构来防止像 Haskell 的惰性列表这样的直接无限循环，或者使用突变通过替换来进行循环。OCaml 的列表既不惰性也不可变，因此您不能编写函数动态构造循环列表。

于 2014-10-21T08:36:13.060 回答
5

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

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、包括电池）使用这种被禁止的艺术。

于 2016-02-15T23:25:13.380 回答
3

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 获得此信息后，它可以为 circle2 创建一个静态地址，并以列表的内存表示。

内存的真实值是1::2::3::circle2，实际上是Node (1, Node (2, Node (3, circle2)))，即A Node with int 1 and a Node of int 2 address and a Node of int 3 address and address of 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

let rec 绑定构造，除了定义递归函数外，还支持某类非函数值的递归定义，比如

let rec name1 = 1 :: name2 and name2 = 2 :: name1 in expr 将 name1 绑定到循环列表 1::2::1::2::…，并将 name2 绑定到循环列表 2::1:: 2::1::…非正式地，接受定义的类由那些定义的名称仅出现在函数体内或作为数据构造函数的参数的定义组成。

如果你let rec用来定义一个绑定，比如说let rec name. 这name只能在函数体或数据构造函数中。

在前面的两个示例中，circle1is 在函数体 ( 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

于 2014-10-21T12:20:18.533 回答