代码之家 › 专栏 › 技术社区 › Abhinav Kaushik

关于懒惰的困惑

lazy-evaluation functional-programming haskell

5

Abhinav Kaushik · 技术社区 · 16 年前

我有一个功能

myLength = foldl (\ x _ -> x + 1) 0

它失败,堆栈溢出,输入约10^6个元素(mylength[1..1000000]失败)。我相信这是因为当我用foldl替换foldl时,thunk的建立起了作用。到现在为止,一直都还不错。

但现在我有了另一个函数来反转列表:

myReverse = foldl (\ acc x -> x : acc) []

使用Lazy版本文件夹( 相反福尔德尔的)

当我这样做的时候 myLength . myReverse $ [1..1000000] . 这次效果不错。我不明白为什么foldl适用于后一种情况而不是前一种情况?

这里要澄清,mylength使用foldl'而myreverse使用foldl'

1 回复 | 直到 15 年前

1

3

Artelius 16 年前

这是我的最佳猜测,尽管我还不是哈斯克尔内部专家。

在构建thunk时,haskell在堆 .

当执行添加时,如 myLength ,它需要使用堆栈作为中间变量。见 this page . Excerpt:

当我们最终评估z1000000时,问题就开始了:

注意z1000000=z999999+ 1000000。所以1000000被推到堆栈上。然后计算Z999999。

注意z999999=z999998+999999。所以999999被推到堆栈上。然后 Z999998评估:

注意Z999998=Z999997+999998 8。所以999998 8被推到堆栈上。然后 Z999997评估:

但是,在执行列表构造时,我认为会发生以下情况(这是猜测的开始):

评估z1000000时:

注意z1000000=1000000: Z999 99。所以1000000是储存在里面的 z1000000,连同一个链接(指针) 到Z99 99 99。然后计算Z999999。

注意Z999999=999999:Z999998。所以999999存储在Z999999中, 以及Z999998的链接。然后评估Z999998。

等。

请注意,Z999999、Z999998等从尚未计算的表达式更改为单个列表项是一个日常的haskell事情:)

因为z1000000、z999999、z999998等都在堆中,所以这些操作不使用任何堆栈空间。QED。