foldl / foldr query

 

I'm a beginner at Haskell, and even after reading several explanations of foldr/foldl, I can't understand why I'm getting different results below. What is the explanation? 

Prelude> foldl (_ -> (+1)) 0 [1,2,3]
4
Prelude> foldr (_ -> (+1)) 0 [1,2,3]
3

Thanks!

In the foldl case, the lambda is being passed the accumulator as the first argument, and the list element as the second. In the foldr case, the lambda is being passed the list element as the first argument, and the accumulator as the second.

Your lambda ignores the first argument, and adds 1 to the second, so in the foldl case you are adding 1 to the last element, and in the foldr case, you are counting the number of elements in the list.

That's because the order of the arguments is flipped in foldl . Compare their type signatures: 

foldl :: (a -> b -> a) -> a -> [b] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b

So you see, in your code using foldl , you repeatly increment the accumulator, ignoring the list. But in the code with foldr , you don't even touch the accumulator, but just increment the element of the list. As the last element is 3 , the result is 3 + 1 = 4 .

You could see your misstake more easy, if you'd use a list of characters aka string instead: 

ghci> foldr (_ -> (+1)) 0 ['a','b','c']
3
ghci> foldl (_ -> (+1)) 0 ['a','b','c']

:1:20:
    No instance for (Num Char)
      arising from the literal `0'
    Possible fix: add an instance declaration for (Num Char)
    In the second argument of `foldl', namely `0'
    In the expression: foldl ( _ -> (+ 1)) 0 ['a', 'b', 'c']
    In an equation for `it':
        it = foldl ( _ -> (+ 1)) 0 ['a', 'b', 'c']
ghci>

The difference is because of two things:

  • You're discarding one input to the accumulating function and applying a constant function to the other.
  • The order of arguments to the accumulating function are different between the two.

    • With the left fold, the accumulator is the argument you discard, so each time you're applying (+1) to the next item in the list and eventually return the last element plus one.

    With the right fold, the accumulator is the argument you keep, so each time you're applying (+1) to the previous result, which is 0 to start with and gets incremented three times (for each item in the list).

    It might be easier to see what's going on here if you use more obviously distinct input values: 

    Prelude> foldl (_ -> (+1)) 100 [5,6,7]
8
Prelude> foldr (_ -> (+1)) 100 [5,6,7]
103

    Again, "last argument plus one" and "length of list plus initial value".

    链接地址: http://www.djcxy.com/p/80726.html

    上一篇: foldl和foldr？

    下一篇: foldl / foldr查询