首页 文章

foldl与具有无限列表的foldr行为

提问于
浏览 次
98

this question中myAny函数的代码使用foldr . 当谓词满足时，它会停止处理无限列表 .

我用foldl重写了它：

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

（请注意，步骤函数的参数已正确反转 . ）

但是，它不再停止处理无限列表 .

我试图在Apocalisp's answer中跟踪函数的执行：

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

但是，这不是函数的行为方式 . 这怎么了？

haskell lazy-evaluation combinators fold

4 回答

  • 1

    fold 的不同似乎是混淆的常见原因，所以这里有一个更概括的概述：

    考虑使用某个函数 f 和种子 z 折叠n个值 [x1, x2, x3, x4 ... xn ] 的列表 .

    foldl是：

    • Left associative ： f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn

    • Tail recursive ：它遍历列表，然后生成值

    • Lazy ：在需要结果之前，不评估任何内容

    • Backwards ： foldl (flip (:)) [] 反转列表 .

    foldr是：

    • Right associative ： f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))

    • Recursive into an argument ：每次迭代都将 f 应用于下一个值以及折叠列表其余部分的结果 .

    • Lazy ：在需要结果之前，不评估任何内容

    • Forwards ： foldr (:) [] 返回一个未更改的列表 .

    这里有一个稍微微妙的点，有时会引起人们的注意：因为 foldl 是 backwards ， f 的每个应用程序被添加到结果的外部;因为它是 lazy ，所以在需要结果之前不会对任何内容进行评估 . 这意味着要计算结果的任何部分，Haskell首先遍历整个列表，构建嵌套函数应用程序的表达式，然后计算最外层函数，根据需要评估其参数 . 如果 f 总是使用它的第一个参数，这意味着Haskell必须一直递归到最里面的术语，然后向后计算 f 的每个应用程序 .

    这显然与大多数功能程序员所熟悉和喜爱的高效尾递归相差甚远！

    实际上，即使 foldl 在技术上是尾递归的，因为整个结果表达式是在评估任何内容之前构建的， foldl can cause a stack overflow!

    另一方面，考虑 foldr . 它也很懒，但因为它运行 forwards ， f 的每个应用程序都会添加到结果的内部 . 因此，为了计算结果，Haskell构造了一个单独的函数应用程序，其第二个参数是折叠列表的其余部分 . 如果 f 在其第二个参数（例如数据构造函数）中是惰性的，则结果将是 incrementally lazy ，折叠的每个步骤仅在需要计算结果的某些部分时计算 .

    因此，当 foldl 没有时，我们可以看到为什么 foldr 有时在无限列表上工作：前者可以懒惰地将无限列表转换为另一个惰性无限数据结构，而后者必须检查整个列表以生成结果的任何部分 . 另一方面， foldr 具有立即需要两个参数的函数，例如 (+) ，与 foldl 非常相似（或者更确切地说，不起作用），在评估它之前构建一个巨大的表达式 .

    所以需要注意的两点是：

    • foldr can transform one lazy recursive data structure into another.

    • Otherwise, lazy folds will crash with a stack overflow on large or infinite lists.

    您可能已经注意到它听起来像 foldr 可以做所有事情 foldl 可以，还有更多 . 这是真的！事实上， foldl is nearly useless!

    但是如果我们想通过折叠大（但不是无限）列表来产生非惰性结果呢？为此，我们想要 strict fold ，其中the standard libraries thoughfully provide：

    foldl'是：

    • Left associative ： f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn

    • Tail recursive ：它遍历列表，然后生成值

    • Strict ：沿途评估每个功能应用程序

    • Backwards ： foldl' (flip (:)) [] 反转列表 .

    因为 foldl' 是 strict ，为了计算结果，Haskell将在每一步评估 f ，而不是让左参数累积一个巨大的，未评估的表达式 . 这给了我们想要的通常，有效的尾递归！换一种说法：

    • foldl' can fold large lists efficiently.

    • foldl' will hang in an infinite loop (not cause a stack overflow) on an infinite list.

    Haskell维基也有a page discussing this .

    回复于
  • 198
    myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

    等等

    直观地说， foldl 始终位于"outside"或"left"上，因此它首先被展开 . 无限广告 .

    回复于
  • 26

    您可以在Haskell的文档here中看到，foldl是尾递归的，如果传递了无限列表，它将永远不会结束，因为它在返回值之前调用自己的下一个参数...

    回复于
  • 9

    我不知道Haskell，但在Scheme中， fold-right 将始终'act'在列表的最后一个元素上 . 因此对于循环列表（与无限循环列表相同）将不起作用 .

    我不确定 fold-right 是否可以写尾递归，但对于任何循环列表，你应该得到堆栈溢出 . fold-left OTOH通常使用尾递归实现，如果不及早终止，它将陷入无限循环 .

    回复于

相关问题