为什么函数concat使用文件夹?为什么不折叠呢? [英] Why does function concat use foldr? Why not foldl'

问题描述

在大多数资源中，建议使用foldl'，但这是在concat中使用foldr而不是foldl'的原因吗?

In most resources it is recommended to use foldl', but that cause of using foldr in concat instead of foldl'?

推荐答案

编辑在这个答案中我谈到了懒惰和生产力，而我的兴奋却忘了jpmariner关注的一个非常重要的观点.他们的答案:左关联(++)是二次时间！

EDIT I talk about laziness and productivity in this answer, and in my excitement I forgot a very important point that jpmariner focuses on in their answer: left-associating (++) is quadratic time!

foldl'是合适的.如果累加器很严格，则必须先消耗整个列表，然后才能给出任何输出. foldl'使用尾部递归来避免在这种情况下炸毁堆栈，但是foldr不会，并且会导致性能下降.另一方面，foldl' 必须以这种方式消耗整个列表.

foldl' is appropriate when your accumulator is a strict type, like most small types such as Int, or even large spine-strict data structures like Data.Map. If the accumulator is strict, then the entire list must be consumed before any output can be given. foldl' uses tail recursion to avoid blowing up the stack in these cases, but foldr doesn't and will perform badly. On the other hand, foldl' must consume the entire list in this way.

foldl f z []      =          z
foldl f z [1]     =        f z 1
foldl f z [1,2]   =     f (f z 1) 2
foldl f z [1,2,3] =  f (f (f z 1) 2) 3

列表的 final 元素是评估最外层应用程序所必需的，因此无法部分使用列表.如果我们使用(++)进行扩展，我们将看到:

The final element of the list is required to evaluate the outermost application, so there is no way to partially consume the list. If we expand this with (++), we will see:

foldl (++) [] [[1,2],[3,4],[5,6]]
    = (([] ++ [1,2]) ++ [3,4]) ++ [5,6]
           ^^

    = ([1,2] ++ [3,4]) ++ [5,6]
    = ((1 : [2]) ++ [3,4]) ++ [5,6] 
                 ^^

    = (1 : ([2] ++ [3,4])) ++ [5,6]
                           ^^

    = 1 : (([2] ++ [3,4]) ++ [5,6])

(我承认，如果您对缺点列表不太满意，这看起来有些不可思议；不过，值得详细了解细节)

(I admit this looks a little magical if you don't have a good feel for cons lists; it's worth getting dirty with the details though)

看看在1冒泡到最前面之前，我们该如何评估每个 (++)(在对它们进行评估时标有^^)?在此之前，1一直隐藏"在功能应用程序下.

See how we have to evaluate every (++) (marked with ^^ when they are evaluated) on the way down before before the 1 bubbles out to the front? The 1 is "hiding" under function applications until then.

foldr对于诸如列表之类的非严格累加器很有用，因为它允许累加器在消耗整个列表之前产生信息，这可以使许多经典的线性空间算法降到恒定空间！这也意味着，如果列表无限，除非您的目标是使用CPU加热房间，否则foldr是您唯一的选择.

foldr, on the other hand, is good for non-strict accumulators like lists, because it allows the accumulator to yield information before the entire list is consumed, which can bring many classically linear-space algorithms down to constant space! This also means that if your list is infinite, foldr is your only choice, unless your goal is to heat your room using your CPU.

foldr f z []      = z 
foldr f z [1]     = f 1 z
foldr f z [1,2]   = f 1 (f 2 z)
foldr f z [1,2,3] = f 1 (f 2 (f 3 z))
foldr f z [1..]   = f 1 (f 2 (f 3 (f 4 (f 5 ...

我们可以很容易地表达最外层的应用程序，而不必查看整个列表.扩展foldr的方式与执行foldl的方式相同:

We have no trouble expressing the outermost applications without having to see the entire list. Expanding foldr the same way we did foldl:

foldr (++) z [[1,2],[3,4],[5,6]]
    = [1,2] ++ ([3,4] ++ ([5,6] ++ []))
    = (1 : [2]) ++ (3,4] ++ ([5,6] ++ []))
                ^^

    = 1 : ([2] ++ ([3,4] ++ ([5,6] ++ [])))

1立即产生 ，而不必评估除第一个以外的任何(++).因为这些(++)都不被评估，并且Haskell是惰性的，所以甚至在消耗更多输出列表之前，不必生成 ，这意味着concat可以在恒定空间中运行对于这样的功能

1 is yielded immediately without having to evaluate any of the (++)s but the first one. Because none of those (++)s are evaluated, and Haskell is lazy, they don't even have to be generated until more of the output list is consumed, meaning concat can run in constant space for a function like this

concat [ [1..n] | n <- [1..] ]

使用严格的语言，这将需要任意长度的中间列表.

which in a strict language would require intermediate lists of arbitrary length.

如果这些减少看起来有些不可思议，并且您想更深入一点，我建议您检查

If these reductions look a little too magical, and if you want to go deeper, I suggest examining the source of (++) and doing some simple manual reductions against its definition to get a feel for it. (Just remember [1,2,3,4] is notation for 1 : (2 : (3 : (4 : [])))).

通常，以下是提高效率的强大经验法则:如果累加器是严格的数据结构，请使用foldl'，否则请使用foldr.而且，如果您看到使用常规foldl的朋友并且不阻止他们，那您是什么样的朋友?

In general, the following seems to be a strong rule of thumb for efficiency: use foldl' when your accumulator is a strict data structure, and foldr when it's not. And if you see a friend using regular foldl and don't stop them, what kind of friend are you?

这篇关于为什么函数concat使用文件夹?为什么不折叠呢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！