当调用一个生成惰性列表的函数时进行函数编程

Question

我可以像这样定义一个无限数据结构，也就是惰性列表。

let 'a lazylist = Succ of 'a * (unit -> 'a lazylist);;

(为什么我不能用() -> 'a lazylist代替unit -> 'a lazylist？(

我理解惰性数据结构的方式是，上面的定义说惰性列表由一个通用元素'a和一个函数unit->'a lazylist的元组组成，当用类型为unit的()调用时，该函数将计算列表中的下一个元素。

因此，例如，我可以生成一个包含每个偶数的列表：

let rec even_list l = 
match l with 
Succ (a, l') -> 
if (a mod 2 = 0) then 
Succ (a, fun() -> even_list (l' ())
else  
even_list (l' ());;

我的理解是：当用单元参数()调用fun() -> even_list (l'()))时，它将用l'的后继调用even_list，并将其作为参数unit：l'()

但是，如果我们给even_list一个仅由不均匀元素组成的lazylist作为自变量，那么else even_list (l'());;部分是否有可能导致堆栈溢出，例如。？而在if语句的then部分，当用()调用时，我们只生成列表的下一个元素——在else部分，我们将无限期地搜索。

Answer 1

首先，您可以使用内置的Seq.t类型，而不是定义自己的惰性列表类型。

其次，函数even_list是尾部递归的，不会导致堆栈溢出。

第三，如果您使用的是OCaml中的Call lazy list函数中提出的take函数，则该函数不是尾递归的，并且消耗堆栈。

您可以编写这个函数的尾部递归版本

let rec take l n (Succ(x,f)) =
if n = 0 then List.rev l
else take (x::l) (n-1) (f ())
let take n l = take [] n l

或定义fold函数

let rec fold_until n f acc (Succ(x,l)) =
if n = 0 then acc
else fold_until (n-1) f (f acc x) (l())

并使用该函数来定义不建立中间列表的打印机。

(这就是为什么通常建议写下一个完全独立的例子，否则问题往往隐藏在问题的隐含上下文中。(