Mistake in this fold implementation

Question

In this lecture about Haskell programming, there is a fold implementation, defined like so :

fold :: (a -> b -> b) -> b  -> [a] -> b
fold f z []     = z
fold f z (x:xs) = f x (fold z f xs)

The idea is to use it to define sum, product, etc...

sum''     = fold (+) 0
product'' = fold (*) 1
length''  = fold addOne 0
 where addOne _ s = 1 + s

There seems to be an inversion between z and f inside the recursion pattern: otherwise, how could z f xs match (a -> b -> b) -> b -> [a]?

In my opinion, the recursion pattern should be

fold f z (x:xs) = f x (fold f z xs)

However, shortly after in the lecture, you can find the following statement:

fold f z [a,b,c] = a `f` (b `f` (c `f` z))

This reinforces the so-called mistake, so I guess there must be a mistake in my head instead!

Shouldn't it be more like the following ?

fold f z [a,b,c] = `f` a (`f` b (`f` c z))

Am I missing a point, or is it a double mistake in the lecture?

Answer 1

There seems to be an inversion between z and f inside the recursion pattern: otherwise how could z f xs match (a -> b -> b) -> b -> [a]?

You're correct, the types don't align, and GHC is quick to let you know if you try to define fold as given:

Couldn't match expected type ‘a -> b -> b’ with actual type ‘b’
  ‘b’ is a rigid type variable bound by
      the type signature for fold :: (a -> b -> b) -> b -> [a] -> b
      at test.hs:1:9
...

However, shortly after in the lecture, you can find the following statement:

fold f z [a,b,c] = a `f` (b `f` (c `f` z))

This reinforces the so-called mistake, so I guess there must be a mistake in my head instead!

Shouldn't it be more like the following ?

fold f z [a,b,c] = `f` a (`f` b (`f` c z))

No. Once you've defined fold correctly, this unfolding of the definition is correct. The author is simply using the backtick notation to use function f as an infix operator:

fold f z [a,b,c] = a `f` (b `f` (c `f` z))

is equivalent to

fold f z [a,b,c] = f a (f b (f c z))

but is perhaps more readable if you think of f as binary function such as (+); compare

fold (+) 0 [1,2,3] = 1 + (2 + (3 + 0))

to the less readable

fold (+) 0 [1,2,3] = (+) 1 ((+) 2 ((+) 3 0))

Answer 2

The code fold f z (x:xs) = f x (fold z f xs) should indeed be fold f z (x:xs) = f x (fold f z xs).

The second part is correct though, since (pay attention to the backticks)

f x y == x `f` y

we have

a `f` (b `f` (c `f` z)) == f a (f b (f c z)))