如何编写一个函数，该函数在每次迭代时都将可变数量的元素附加到惰性列表？

Question

动机是：编写一个懒惰列表，其元素都是0和1的所有可能组合，即[0]，[1]，[0; 0]，[0; 1]等。

在OCaml中工作，我编写了辅助函数，用于生成给定n的长度为n + 1的排列列表，并将列表转换为惰性列表。问题来自下面的代码块中的最终函数：

type 'a seq =
    | Nil
    | Cons of 'a * (unit -> 'a seq)

let rec adder = function
    | [] -> [] 
    | [[]] -> [[0];[1]]
    | xs::ys -> (0::xs)::(1::xs)::(adder ys)

let rec listtoseq = function
    | [] -> Nil
    | xs::ys -> Cons(xs, fun () -> listtoseq ys)

let rec appendq xq yq =
    match xq with
        | Nil -> yq
        | Cons (x, xf) -> Cons (x, fun() -> appendq (xf ()) yq)

let genlist xs = appendq (listtoseq xs) (genlist (adder xs))

调用Genlist [[0]; [1]]导致堆栈溢出。问题似乎是，由于genlist是一个无限循环，我想延迟评估，但是需要评估才能使appendq起作用。

如果这是一次可以将一个元素添加到惰性列表的问题，我可以解决，但是我认为困难在于必须同时添加每组长度为n的排列，因此我不这样做除了使用附加函数，还知道其他解决方案。

Answer 1

查看您的问题的一种方法是appendq不够懒。如果使用以下类型定义函数appendqf，则可以使事情正常进行：

'a seq -> (unit -> 'a seq) -> 'a seq

换句话说，第二个参数不是序列。这是一个返回序列的函数。

（（请注意，此类型unit -> 'a seq实际上是在Cons内部显示的。）

我尝试过，它对我有用。