为什么Haskell的折叠器不会同时运行Scala实现？

发布时间：2020-12-16 09:21:04 所属栏目：安全来源：网络整理

导读：我正在读 FP in Scala. 练习3.10说foldRight溢出(见下图). 据我所知,哈斯克尔的折扣并不是这样. http://www.haskell.org/haskellwiki/ -- if the list is empty,the result is the initial value z; else-- apply f to the first element and the result of

我正在读 FP in Scala.

练习3.10说foldRight溢出(见下图).
据我所知,哈斯克尔的折扣并不是这样.

http://www.haskell.org/haskellwiki/

-- if the list is empty,the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty,the result is the initial value; else
-- we recurse immediately,making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

这种不同的行为如何可行？

造成这种不同行为的两种语言/编译器有什么区别？

这个差异来自哪里？平台？语言？编译器？

是否可以在Scala中编写一个堆栈安全的foldRight？如果是,怎么样？

解决方法

哈斯克尔很懒.定义

foldr f z (x:xs) = f x (foldr f z xs)

告诉我们,具有非空列表xs的foldr f z xs的行为由组合函数f的懒惰决定.

特别是调用foldr fz(x：xs)在堆上分配一个thunk,{foldr fz xs}(写一个持有表达式…的thunk的{…}),并用两个参数调用f和thunk.接下来会发生什么,是f的责任.

特别是,如果它是一个懒惰数据构造函数(例如(:)),它将立即返回到foldr调用的调用者(构造函数的两个插槽由两个值填充(引用)).

如果f确实要求其正确的价值,最小化编译器优化,根本不需要创建任何thunk(或者一个,最多的是当前的),因为foldr fz xs的值是立即需要的,通常的stack-基于评估可以使用：

foldr f z [a,b,c,....,n] ==
    a `f` (b `f` (c `f` (... (n `f` z)...)))

因此,在极长的输入列表中使用严格的组合功能时,折叠器确实会导致SO.但是,如果组合功能没有要求权利的价值,或者只是要求其一部分,评价将被暂停,并且由f创建的部分结果将立即返回.与左侧的参数相同,但是他们已经可以在输入列表中成为thunk.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!