如何编写函数以在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（请参阅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的列表不是惰性的也不是可变的，因此您不能编写动态构造循环列表的函数。

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、Batteries）使用这种禁忌艺术。