调用生成惰性列表的函数时发生堆栈溢出？

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'())) 时，它将调用 even_list 与 l' 的后继者 [=] 21=] 作为参数：l'()

但是如果我们给 even_list 一个只包含不均匀元素的惰性列表作为参数，else even_list (l'());; 部分是否有可能导致堆栈溢出？而在 if 语句的 then 部分中，我们仅在使用 () 调用时生成列表的下一个元素 - 在 else 部分中，我们将无限期地搜索。

Answer 1

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

其次，你的函数 even_list 是 tail-recursive 并且不会导致堆栈溢出。

第三，如果你使用的是中提出的take函数，就是这个函数不是tail-recursive并且消耗堆栈。

您可以编写此函数的 tail-recursive 版本

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())

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

（这就是为什么通常建议 write-down 一个完整的 self-contained 示例，否则问题往往隐藏在问题的隐式上下文中。）

调用生成惰性列表的函数时发生堆栈溢出？

Stack Overflow when calling a function that generates a lazy list?

functional-programming

ocaml

lazy-evaluation