Trying this in ghci:

foldl (:) [1] [2,3,4]

which gives the following error:

<interactive>:51:7: error:
    • Couldn't match type ‘a’ with ‘[a]’
      Expected: [a] -> [[a]] -> [a]
        Actual: [a] -> [[a]] -> [[a]]
      ‘a’ is a rigid type variable bound by
        the inferred type of it :: [a]
        at <interactive>:51:1-21
    • In the first argument of ‘foldl’, namely ‘(:)’
      In the expression: foldl (:) [1] [2, 3, 4]
      In an equation for ‘it’: it = foldl (:) [1] [2, 3, 4]
    • Relevant bindings include it :: [a] (bound at <interactive>:51:1)

But the same thing works with foldr

foldr (:) [1] [2,3,4]

which outputs [2,3,4,1]

Shouldn't the foldl output (above) be [1,2,3,4]? As per my understanding, the only difference between foldl and foldr is where the accumulator is placed so I am not understanding this error.

CodePudding user response：

The signatures of foldl and foldr` differ. Indeed:

foldl :: Foldable f => (b -> a -> b) -> b -> t a -> b
foldr :: Foldable f => (a -> b -> b) -> b -> t a -> b

Notice the different order of a and b in the "fold function" (first parameter).

This is likely to stress that foldl f z [x1, x2, …, xn] is defined as:

foldl f z [x1, x2, …, xn] = f (… (f (f z x1) x2) …) xn

whereas for foldr f z [x1, x2, …, xn], we get:

foldr f z [x1, x2, …, xn] = f x1 (f x2 (… (f xn z) …))

You thus can work with:

foldl (flip (:)) [1] [2,3,4]

But this will not give the same result, since we construct:

foldl (flip (:)) [1] [2,3,4] = 4 : (3 : (2 : [1]))
                             = [4, 3, 2, 1]