foldr and foldr1 Haskell

Question

I am trying to dive deep in the folds, considering it seems a very powerful asset to me. However, can you help me with this:

foldr  (/) 2 [1,2,3] -- (1/(2/(3/2))), result 0,75 {where 2 is base)
foldr1 (/)   [2,2,3] -- (1/(2/(3/2))), result 3.00 {where 2 is base)

I think I am seriously overseeing an essential difference between the folds. Thx

Answer 1

In general

foldr1 op [y1, ..., yn, x]

is essentially the same as

foldr op x [y1, ..., yn]

as long as n >= 1. That is, in your special case

foldr1 (/) [2, 2, 3]

will evaluate to 2/(2/3) = 3.

With the division operator, it's a bit boring, because

foldr1 (/) [y, y, x1, ... , xn]
  = y/(y/(foldr1 (/) [x1, ..., xn]))
  = foldr1 (/) [x1, ..., xn]

for all n >= 1. So, in your example, it should just return the result of

foldr1 (/) [3]

which is of course 3.0, and it does indeed evaluate to 3.0.

Here is less degenerate example:

foldr1 (/) [2, 3, 5, 7] --  evals to 0.47619047619047616

Here, it gives the same result as 2 / (3 / (5 / 7)), which is in turn the same as

foldr (/) 7 [2, 3, 5]

I hope it clarifies the order of evaluation a little bit.

Answer 2

foldr :: (a -> b -> b) -> b -> [a] -> b has as implementation:

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

So that means that if we enter foldr f z [x1, x2, x3], then it is evaluated as:

   foldr f z [x1, x2, x3]
-> f x1 (foldr f z [x2, x3])
-> f x1 (f x2 (foldr f z [x3]))
-> f x1 (f x2 (f x3 (foldr f z [])))
-> f x1 (f x2 (f x3 z))

So for your example that will evaluate to:

  (/) 1 ((/) 2 ((/) 3 2))
= 1 / (2 / (3 / 2))
= 1 / (2 / 1.5)
= 1 / 1.33333...
= 0.75

The foldr1 :: (a -> a -> a) -> [a] -> a function is almost similar, except that in case we see the a 1-element list, we return that element, so the difference is:

foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ [x] = x
foldr f (x:xs) = f x (foldr1 f xs)

So that means that for a foldr1 f [x1, x2, x3] we get:

   foldr1 f [x1, x2, x3]
-> f x1 (foldr1 f [x2, x3])
-> f x1 (f x2 (foldr1 f [x3]))
-> f x1 (f x2 x3))

So for the sample input, we get:

  (/) 2 ((/) 2 3)
= 2 / (2 / 3)
= 2 / 0.6666...
= 3.0

So in case z and xi have the same type, then foldr f z [x1, ..., xn] is equal to foldr1 f [x1, ..., xn, z].