1

this is the type of foldr function.

(a -> b -> b) -> b -> [a] -> b

what is this type ? what are the arguments the function gets? does it get 2 or 3 arguments? and what is the return value?

I know that :

 (a -> b -> b) -  is the function foldr gets (like multiplication)
 b - is the neutral value (such as 1 in multiplication)

1 Answer 1

5

If you have experience with imperative languages such as Java and Python, you can view it like this:

foldr takes three arguments: A function, an identity value, and a list. It then returns an accumulated value.

You're right that a -> b -> b is the function, and b is the identity value. Then [a] is the list, and the second b is the return value, which is the result of the function.

Example of this:

         function
           |   identity value
           |    |  list
           |    |   |
           v    v   v
> foldr   (*)   1   [1, 2, 3, 4]

24  <-- return value

If you have experience with functional programming, you might instead want to view it like this:

foldr takes two arguments: A combining function and an identity value. It then returns a function that takes a list and returns an accumulated value.

In this case, a -> b -> b is still the combining function and b is the identity value. The return value then becomes [a] -> b, which is the function that takes a list and returns an accumulated value.

Example of this:

                        combining function
   returned function      |    identity value
       |                  |     |
       v                  v     v
> let multiply = foldr   (*)    1

> -- since the returned function is of type [a] -> b, we give
> -- it a list and it gives us the accumulated value back
> multiply [1, 2, 3, 4]
24
3
  • 2
    And to someone with an ML background, Haskell's foldr takes one argument.
    – dfeuer
    May 10, 2014 at 9:36
  • @dfeuer Technically it takes one argument in Haskell as well, but I find that interpretation meaningless for foldr specifically, since you usually want to specify both combination function and identity element. It's rare for you to want to specify the combination function and then let someone else decide on the identity element, simply because the common binary operations have an inherent identity element. Given that a Foldable instance has a possible minimal implementation of foldMap, I get the feeling it makes a lot of sense to group the append operation and the identity element.
    – kqr
    May 10, 2014 at 9:40
  • 3
    it's not identity value; it's default value. foldr (:) [] and foldr (:) [1,2,3] both make sense.
    – Will Ness
    May 10, 2014 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.