3

I understand simple foldr statements like

foldr (+) 0 [1,2,3]

However, I'm having trouble with more complicated foldr statements, namely ones that take 2 parameters in the function, and with / and - computations. Could anyone explain the steps that occur to get these answers? 

foldr (\x y -> (x+y)*2) 2 [1,3] = 22

foldr (/) 2 [8,12,24,4] = 8.0

Thanks.

duplode
  • 33,731
  • 7
  • 79
  • 150
p0ny
  • 317
  • 2
  • 10

3 Answers3

4

The function argument of a fold always takes two arguments. (+) and (/) are binary functions just like the one in your second example.

Prelude> :t (+)
(+) :: Num a => a -> a -> a

If we rephrase the second example as

foldr f 2 [1,3]
    where
    f x y = (x+y)*2

we can expand the right fold using exactly the same scheme we would use for (+):

foldr f 2 [1,3]
foldr f 2 (1 : 3 : [])
1 `f` foldr f 2 (3 : [])
1 `f` (3 `f` foldr f 2 [])
1 `f` (3 `f` 2)
1 `f` 10
22

It is worth noting that foldr is right-associative, which shows in how the parentheses nest. Conversely, foldl, and its useful cousin foldl', are left-associative.

duplode
  • 33,731
  • 7
  • 79
  • 150
4

The foldr function is defined as follows:

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

Now consider the following expression:

foldr (\x y -> (x + y) * 2) 2 [1,3]

We'll give the lambda a name:

f x y = (x + y) * 2

Hence:

foldr f 2 [1,3]
-- is
f 1 (foldr f 2 [3])
-- is
f 1 (f 3 (foldr f 2 []))
-- is
f 1 (f 3 2)
-- is
f 1 10
-- is
22

Similarly:

foldr (/) 2 [8,12,24,4]
-- is
8 / (foldr (/) 2 [12,24,4])
-- is
8 / (12 / (foldr (/) 2 [24,4]))
-- is
8 / (12 / (24 / (foldr (/) 2 [4])))
-- is
8 / (12 / (24 / (4 / (foldr (/) 2 []))))
-- is
8 / (12 / (24 / (4 / 2)))
-- is
8 / (12 / (24 / 2.0))
-- is
8 / (12 / 12.0)
-- is
8 / 1.0
-- is
8.0

Hope that helped.

Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
2

You can think of foldr, maybe, and either as functions that replace the data constructors of their respective types with functions and/or values of your choice:

data Maybe a = Nothing | Just a

maybe :: b -> (a -> b) -> Maybe a -> b
maybe  nothing _just Nothing  = nothing
maybe _nothing  just (Just a) = just a

data Either a b = Left a | Right b

either :: (a -> c) -> (b -> c) -> Either a b -> c
either  left _right (Left  a) = left  a
either _left  right (Right b) = right b

data List a = Cons a (List a) | Empty

foldr :: (a -> b -> b) -> b -> List a -> b
foldr cons empty = loop
  where loop (Cons a as) = cons a (loop as)
        loop Empty       = empty

So in general, you don't really have to think about the recursion involved, just think of it as replacing the data constructors:

foldr f nil (1 : (2 : (3 : []))) == (1 `f` (2 `f` (3 `f` nil)))
lpsmith
  • 707
  • 3
  • 8