Haskell 的无限列表, 底层实现是怎样的?

Question

看到一个Scheme的实现,用了delay这个函数...https://www.shido.info/lisp/scheme_lazy_e.html
但是底层,比如说编译到IR或者汇编,这种功能怎样实现?

Answer 1

惰性求值的底层其实是借助了thunk。粗浅的解释就是一个求值用的函数和它的自由变量环境的结合。每一个表达式在其值被需要之前，总是先存储为一个thunk，一旦其值必须要被求解出来，就强迫执行求值过程。比如说，如果有这样的列表：list::[Integer]list=[1..]它首先会被实现为对系统函数enumFrom的调用，调用的结果类似这样：enumFrom::Integer->[Integer]enumFromn=n:enumFrom(n+1)list=enumFrom1=1:enumFrom2=1:2:enumFrom3=1:2:3:enumFrom4--onandon...其中每个enumFrom的调用都会被实现为一个thunk。我们以take5list为例。take函数用(:)进行模式匹配，类似于：take::Int->[a]->[a]take0_=[]taken(x:xs)=x:take(n-1)xstake__=error"Invalidcalloftake."需要对列表进行模式匹配时，将要求从thunk中匹配一个(:)运算符（构造器），这时thunk求值一层，从list展开成1:thunk2，模式匹配成功，取出了1。take函数会要求进一步匹配，新thunk（即thunk2）也会被求值，又产生新的thunk。当thunk中的值不再需要时，就不会进一步求值了。这样，无穷的求解步骤就被拆分开来，总是用一个thunk来表达无穷的部分，就不会耗尽内存了。

Answer 2

惰性计算（LazyEvaluation）是haskell的一大特点之一。无限列表也是LazyEvaluation的一种表现。它的底层实现感觉上没那么重要吧。了解概念就OK了，反正它很快，O(1)的时间复杂度、空间复杂度。