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

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

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

（请注意，此类型 unit -> 'a seq 是实际出现在 Cons 中的类型。）

我试过了，对我有用。

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

How to write a function that appends a variable number of elements to a lazy list with each iteration?

functional-programming

ocaml

ml