ocaml - 流(又名 "lazy lists")和尾递归

Question

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

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

我的问题是:如何定义一个采用非空(且非惰性)列表l的尾递归函数lcycle > 作为参数，并返回与重复循环元素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

...但我还没能写出一个尾递归的。

基本上，我遇到了惰性求值是通过表单的构造实现的问题

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

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

假设上面定义了lazylist类型，是否可以定义尾递归lcycle？或者这对于 OCaml 来说本质上是不可能的吗？

编辑:我的动机不是通过使其尾递归来“修复”我的 lcycle 实现，而是找出它是否甚至可能给定上面的lazylist 的定义，实现lcycle 的尾递归版本。因此，指出我的 lcycle 很好就错过了我想要表达的意思。很抱歉，我在原来的帖子中没有充分阐明这一点。

---

这个ltake的实现，以及上面lazylist类型的定义，来自here :

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