为什么Haskell的折叠器不是stackoverflow而是同一个Scala实现呢？
jhe*_*dus 15 haskell functional-programming scala fold
练习3.10表示foldRight溢出(见下图).据我所知,然而foldr在Haskell中没有.
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？如果有,怎么样？
Wil*_*ess 20
哈斯克尔很懒.定义
foldr f z (x:xs) = f x (foldr f z xs)
告诉我们,foldr f z xs非空列表的行为xs是由组合函数的懒惰决定的f.
特别是调用foldr f z (x:xs)只在堆上分配一个thunk,{foldr f z xs}({...}为持有表达式的thunk 编写...),并f使用两个参数调用- x以及thunk.接下来会发生什么,是f责任.
特别是,如果它是一个惰性数据构造函数(例如(:)),它将立即返回到调用的foldr调用者(构造函数的两个插槽由两个值填充(引用)).
如果f确实在右边需要它的值,那么最少的编译器优化就不应该创建任何thunks(或者一个,最多 - 当前的那个),因为foldr f z xs需要立即使用值,并且可以使用通常的基于堆栈的评估:
foldr f z [a,b,c,....,n] ==
a `f` (b `f` (c `f` (... (n `f` z)...)))
因此foldr,当在极长输入列表上使用严格组合功能时,确实可以导致SO.但是,如果组合函数不立即要求其右侧的值,或者只需要其中的一部分,则评估将暂停在thunk中,并且f将立即返回由创建的部分结果.与左侧的参数相同,但它们已经可能在输入列表中变为thunks.
- `foldr(+)0 [1..100000000000]`.因为`(+)`是严格的.但是`foldr(:) [] [1..100000000000]`只会返回`1:{foldr(:) [] [2..100000000000]}`,因为`(:)`是一个懒惰的数据构造函数(它不要求其参数的完整值,只是在其两个字段中存储指向未来计算的暂停的指针,`head`和`tail`(或Lisp中的`car`和`cdr`). (3认同)
- "thunk"是["思考的方言过去和过去分词"](http://www.merriam-webster.com/dictionary/thunk).即表达式在第一次被需要之前不被评估,然后它*被*评估并且其结果值被存储 - 所以下次需要它时我们将不必"思考"它,它将会是"thunk".或者故事如此. (2认同)
Don*_*art 19
哈斯克尔很懒.所以foldr在堆上分配,而不是堆栈.根据参数函数的严格性,它可以分配单个(小)结果或大结构.
与严格的尾递归实现相比,你仍然在丢失空间,但它看起来并不那么明显,因为你已经为堆交换了堆栈.
请注意,这里的作者并未引用scala标准库中的任何foldRight定义,例如List上定义的定义.它们指的是他们在3.4节中给出的foldRight的定义.
scala标准库通过反转列表(可以在常量堆栈空间中完成)以foldLeft的形式定义foldRight,然后调用foldLeft,并使传递函数的参数反转.这适用于列表,但不适用于无法安全反转的结构,例如:
scala> Stream.continually(false)
res0: scala.collection.immutable.Stream[Boolean] = Stream(false, ?)
scala> res0.reverse
java.lang.OutOfMemoryError: GC overhead limit exceeded
现在,让我们想想应该是这样操作的结果:
Stream.continually(false).foldRight(true)(_ && _)
答案应该是假的,流中有多少假值或者如果它是无限的,如果我们要将它们与一个连接组合,结果将是错误的.
haskell当然得到这个没有问题:
Prelude> foldr (&&) True (repeat False)
False
这是因为两个重要的事情:haskell的foldr将从左到右遍历流,而不是从右到左,默认情况下haskell是懒惰的.这里的第一个项目,折叠器实际上从左到右遍历列表可能会让一些想到正确折叠的人从右边开始感到惊讶或混淆,但右折叠的重要特征不是它开始的结构的哪一端在,但在相关性的方向.所以给出一个列表[1,2,3,4]和一个名为op左侧的折叠
((1 op 2) op 3) op 4)
右折是
(1 op (2 op (3 op 4)))
但评估的顺序无关紧要.所以作者在第3章中所做的是给你一个从左到右遍历列表的折叠,但是因为scala默认是严格的,所以我们仍然无法遍历我们的无限谬误流,但是有一些耐心,他们将在第5章中得到:)我将给你一个偷看,让我们看看foldRight之间的差异,因为它在标准库中定义,并且在scalaz中的可折叠类型类中定义:
这是scala标准库的实现:
def foldRight[B](z: B)(op: (A, B) => B): B
这是scalaz的可折叠的定义:
def foldRight[B](z: => B)(f: (A, => B) => B): B
区别在于Bs都是懒惰的,现在我们再次折叠无限流,只要我们在第二个参数中给出一个足够懒的函数:
scala> Foldable[Stream].foldRight(Stream.continually(false),true)(_ && _)
res0: Boolean = false