流(又称“惰性列表”)和尾递归

Question

此问题使用以下“惰性列表”(又名“流”)类型：

type 'a lazylist = Cons of 'a * (unit -> 'a lazylist)

我的问题是:如何定义一个尾部递归函数lcycle，它以一个非空(和非惰性)列表l作为参数，并返回对应于在元素l上反复循环的lazylist。例如：

# ltake (lcycle [1; 2; 3]) 10;;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]

(ltake是List::take的一个懒散的模拟；我在文章末尾给出了一个实现。)

我已经实现了几个非尾递归的lcycles版本，例如：

let lcycle l =
  let rec inner l' =
    match l' with
    | []   -> raise (Invalid_argument "lcycle: empty list")
    | [h]  -> Cons (h, fun () -> inner l)
    | h::t -> Cons (h, fun () -> inner t)
  in inner l

...but我还没有写一个尾递归的.

基本上，我遇到了这样的问题:惰性计算是通过表单的构造来实现的

Cons (a, fun () -> <lazylist>)

这意味着我的所有递归调用都发生在这样的构造中，这与尾递归不兼容。

假设上面定义的lazylist类型，是否可以定义一个尾递归lcycle？或者这本质上是OCaml不可能实现的？

编辑:我在这里的动机不是通过使lcycle的尾递归来“修复”我的实现，而是想知道，考虑到上面关于lcycle的定义，是否甚至可以实现lazylist的尾递归版本。因此，指出我的lcycle是好的，错过了我想要达到的目标。很抱歉，我在最初的帖子中没有充分说明这一点。

ltake的这个实现以及上面lazylist类型的定义来自于这里。

let rec ltake (Cons (h, tf)) n =
  match n with
    0 -> []
  | _ -> h :: ltake (tf ()) (n - 1)

Answer 1

我看不出这个定义有什么问题。对inner的调用在lcycle返回之前不会被调用的函数中。因此，不存在堆栈安全问题。

下面是将空列表测试从惰性循环中移出的替代方案：

let lcycle = function
  | [] -> invalid_arg "lcycle: empty"
  | x::xs ->
    let rec first = Cons (x, fun () -> inner xs)
    and inner = function
      | [] -> first
      | y::ys -> Cons (y, fun () -> inner ys) in
    first

Answer 2

问题是你在试图解决一个根本不存在的问题。of_list函数不会占用任何堆栈空间，这就是懒散列表如此优秀的原因。让我来解释一下这个过程。当您将of_list函数应用于非空列表时，它会创建一个列表头的Cons和一个闭包，该闭包捕获对列表尾部的引用。过了一会儿，它又回来了。没别的了。因此，它只需要少量的内存，而且没有一个使用堆栈。一个单词包含x值，另一个包含闭包，它只捕获指向xs的指针。

然后，解构这对，得到现在可以使用的值x，接下来是函数，这实际上是一个闭包，当调用它时，它将被应用到一个列表，如果它是非空的，将返回另一个Cons。请注意，以前的缺点将被销毁为垃圾，所以新的内存将不会被使用。

如果您不相信，您可以构造一个永远不会终止的of_list函数(即循环列表)，并使用一个iter函数打印它。它将永远运行，不带任何记忆。

type 'a lazylist = Cons of 'a * (unit -> 'a lazylist)

let of_list lst =
  let rec loop = function
    | [] -> loop lst
    | x :: xs -> Cons (x, fun () -> loop xs) in
  loop lst

let rec iter (Cons (a, next)) f =
  f a;
  iter (next ()) f