0

So I came across the foldr function in Haskell which from what I pick up, you can use to calculate the product and sum of a list:

foldr f x xs

foldr (*) 1 [1..5] = 120
foldr (+) 0 [1..5] = 15

And adding numbers onto the x part would like, add on to the overall sum or multiply onto the final product

What does foldr actually do and why would anyone use it instead of the built in functions 'sum' or 'product' etc?

HJGBAUM
  • 297
  • 5
  • 16
  • 1
    `foldr` **is** in many ways *the* function around *lists* - why you would use this over `sum` and `product`? Well because you can use it to define those functions (but you are right - you would not - you would use those for readability) – Random Dev May 01 '16 at 14:54
  • 7
    aside from this there are *many* questions just like this - for example: https://stackoverflow.com/questions/1757740/how-foldr-works (possible duplicate) – Random Dev May 01 '16 at 14:55
  • 1
    You wouldn't use `foldr` for summation anyway, you'd use [`foldl'`](https://wiki.haskell.org/Foldr_Foldl_Foldl'). – Chris Martin May 01 '16 at 15:12

2 Answers2

2

sum and product are themselves defined using fold (foldl, not foldr, but let's set aside that distinction for now), so in a sense you are using fold when using those functions. Likewise or, and, concat and many more are all defined using folds as well. So that's already one reason for folds to exist: many of the standard functions can be defined using them instead of having redundant code.

So when would you use folds directly? When doing something that there isn't already a specific function for, i.e. when you want to combine the elements of the list using something other than + or * (or ||, && or ++).

Say you have a list of single-digit numbers and you want to "concatenate" them into one number:

concatDigits = foldl (\acc d -> d + acc * 10) 0

Now concatDigits [1,2,3] gives you 123.

Or you've defined some datastructure and you want to convert lists to it:

fromList = foldr insert empty`

In fact that's how fromList is commonly defined for many data structures.

sepp2k
  • 363,768
  • 54
  • 674
  • 675
0

The Wikipedia entry has a good illustration of what foldr does to a list and how it differs from foldl.

The list [1,2,3] is generated by the cons operator (:) and the empty list [] by this expression tree:

    :
   / \
  1   :
     / \
    2   :
       / \
      3   []

foldr f z replaces the cons operator nodes with f and the empty list with z:

enter image description here

By contrast, foldl f z reorients the expression tree and repositions the zero element at the opposite end of the computation:

enter image description here

Some observations:

  1. Note that foldr (:) [] leaves a list unchanged:

    foldr (:) [] [1..10] == [1..10]

This makes sense since we are simply replacing the cons operator with itself and the empty list with the empty list and thus not changing anything.

  1. If we replace the empty list with some other list we should be able to append two lists, e.g.:

    foldr (:) [9,8,7] [1,2,3] == [1,2,3,9,8,7]

  2. The cons operator may be thought of a way to add an element to a list:

    (:) :: a -> [a] -> [a]

If we define f as:

    f :: Int -> [Int] -> [Int]
    f a as = [0] ++ [a] ++ as

then foldr f [] will prepend a 0 before each element of the input list:

    foldr f [] [1,2,3] == [0,1,0,2,0,3]

  1. Data.Set has a function insert whose signature is structually similar to that of (:):

    insert :: Ord a => a -> Set a -> Set a

Indeed, we can convert a list to a Set using foldr

    import qualified Data.Set as S

    foldr S.insert S.empty [1,2,3]

Note how the empty list is replaced with the empty set - S.empty. This is the idiomatic approach to building up data structures one element at a time - e.g. hash maps, tries, trees, etc.

ErikR
  • 51,541
  • 9
  • 73
  • 124