关于懒惰
混乱我有一个函数关于懒惰
myLength = foldl (\ x _ -> x + 1) 0
从而未能与大约10^6个元素(myLength [1..1000000]失败)输入堆栈溢出。我相信这是因为当我用foldl'替换foldl时,thunk的构建起作用。 目前为止这么好。
但现在我有另一个函数以逆转列表:
myReverse = foldl (\ acc x -> x : acc) []
它使用懒惰版本与foldl(而不是与foldl的“)
当我做 myLength . myReverse $ [1..1000000]
。 这次它工作正常。我不明白为什么foldl适用于后一种情况而不适用于前者?
在此澄清myLength使用与foldl”,而myReverse使用与foldl
这是我最好的猜测,虽然我对哈斯克尔内部没有专家(还)。
在构建thunk时,Haskell分配堆上的所有中间累加器变量。
当执行myLength
中的添加时,它需要使用中间变量的堆栈。见this page。摘录:
注意z1000000 = z999999 + 1000000于是1000,000压栈:
当我们最终评估z1000000的问题开始。然后评估z999999。
请注意,z999999 = z999998 + 999999. 因此999999被压入堆栈。然后 z999998被评估:
请注意,z999998 = z999997 + 999998. 因此,999998被推入堆栈。然后 z999997评价:
但是,执行列表构造的时候,这就是我认为发生(这是猜测开始的地方):
当评估z1000000:
注意z1000000 = 1000000: z999999。所以1000000被存储在 z1000000内,以及链接(指针) 到z999999。然后评估z999999。
请注意,z999999 = 999999:z999998。 因此,999999存储在z999999, 内,并附有指向z999998的链接。然后 z999998被评估。
等
注意z999999,z999998等。从尚未评估的表达式转换为单个列表项是Haskell的日常工作:)
由于z1000000,z999999,z999998等都在堆上,因此这些操作不使用任何堆栈空间。 QED。
实际上,'(:)'的两个参数都存储为指针,而不仅仅是尾巴。换句话说'(+)'在它的两个参数中都是严格的(它们需要被充分评估),但是(())在它的参数中是懒惰的(它们可以是thunk)。 – 2010-05-25 12:08:26
这说得很好。 – Artelius 2010-05-25 12:12:43
非常感谢!任何指针/链接更好地理解thunk(懒惰eval)。 – 2010-05-25 12:15:59
我的不好!纠正它 – 2010-05-25 11:29:45
两种情况下,我得到一个堆栈溢出异常。 – dave4420 2010-05-25 11:43:00
不,这只是你正在查看的网站顶部的徽标;)(我没有得到myReverse的例外) – Artelius 2010-05-25 11:51:14