How does a folding warehouse work?

Question

Can someone explain how foldr works?

Take the following examples:

 Prelude> foldr (-) 54 [10, 11] 53 Prelude> foldr (\xy -> (x+y)/2) 54 [12, 4, 10, 6] 12.0 

I got confused in these executions. Any suggestions?

Answer 1

foldr starts at the right end of the list and combines each entry in the list with the battery value using the function you give it. The result is the final value of the battery after "folding" in all elements of the list. His type:

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

and from this you can see that the list item (type a ) is the first argument of this function, and the battery (type b ) is the second.

For your first example:

 Starting accumulator = 54 11 - 54 = -43 10 - (-43) = 53 ^ Result from the previous line ^ Next list item 

So your answer was 53.

Second example:

 Starting accumulator = 54 (6 + 54) / 2 = 30 (10 + 30) / 2 = 20 (4 + 20) / 2 = 12 (12 + 12) / 2 = 12 

So, the result is 12.

Edit: I wanted to add that for the end lists. foldr can also work with endless lists, but it’s best that I can think of a final case.

Answer 2

The easiest way to understand foldr is to rewrite the list that you add without sugar.

 [1,2,3,4,5] => 1:(2:(3:(4:(5:[])))) 

now what foldr fx does is that it replaces each : with f in the form of an infix and [] with x and evaluates the result.

For example:

 sum [1,2,3] = foldr (+) 0 [1,2,3] [1,2,3] === 1:(2:(3:[])) 

So

 sum [1,2,3] === 1+(2+(3+0)) = 6 

Answer 3

This helps to understand the difference between foldr and foldl . Why is foldr called "roll right"?

Originally, I thought it was because it consumes elements from right to left. However, both foldr and foldl consume the list from left to right.

• foldl is evaluated from left to right (left associative)
• foldr is evaluated from right to left (right associative)

We can make this difference understandable with an example that uses an operator for which associativity takes place. We could use a human example, for example, the operator, "eats":

 foodChain = (human : (shark : (fish : (algae : [])))) foldl step [] foodChain where step eater food = eater `eats` food -- note that "eater" is the accumulator and "food" is the element foldl `eats` [] (human : (shark : (fish : (algae : [])))) == foldl eats (human `eats` shark) (fish : (algae : [])) == foldl eats ((human `eats` shark) `eats` fish) (algae : []) == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) [] == (((human `eats` shark) `eats` fish) `eats` algae) 

The semantics of this foldl as follows: a person eats some kind of shark, and then the same person who ate a shark, then eats fish, etc. The eater is the battery.

Compare this to:

 foldr step [] foodChain where step food eater = eater `eats` food. -- note that "eater" is the element and "food" is the accumulator foldr `eats` [] (human : (shark : (fish : (algae : [])))) == foldr eats (human `eats` shark) (fish : (algae : [])))) == foldr eats (human `eats` (shark `eats` (fish)) (algae : []) == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) [] == (human `eats` (shark `eats` (fish `eats` algae) 

The semantics of this foldr as follows: a person eats a shark that has already eaten a fish that has already eaten some algae. Food is a battery.

Both foldl and foldr "separate" the eaters from left to right, so there is no reason we call foldl as the "left fold". Instead, the order of evaluation makes sense.

Answer 4

Think of foldr very definition :

  -- if the list is empty, the result is the initial value z foldr fz [] = z -- if not, apply f to the first element and the result of folding the rest foldr fz (x:xs) = fx (foldr fz xs) 

So, for example, foldr (-) 54 [10,11] should equal (-) 10 (foldr (-) 54 [11]) , that is, expand again, equal to (-) 10 ((-) 11 54) . Thus, the internal operation 11 - 54 , i.e. -43; and external operation 10 - (-43) , i.e. 10 + 43 , so 53 , as you noticed. Follow the similar steps for your second case, and again you will see how the result is formed!

Answer 5

foldr means a reset on the right, so foldr (-) 0 [1, 2, 3] creates (1 - (2 - (3 - 0))) . In comparison, foldl produces (((0 - 1) - 2) - 3) .

When the operators are not commutative foldl and foldr will get different results.

In your case, the first example expands to (10 - (11 - 54)) , which gives 53.

Answer 6

A simple way to understand foldr is as follows: it replaces each list constructor with the application of the provided function. Your first example will be translated into:

10 - (11 - 54)

from

10 : (11 : [])

The good advice I got from Haskell Wikibook can be helpful here:

Typically, you should use foldr in lists, which can be infinite, or when the fold creates a data structure and foldl' if the list is known as finite and reduces to a single value. foldl (no tick) should rarely be used at all.

Answer 7

I always thought http://foldr.com to be a fun illustration. See post Lambda the Ultimate .

Answer 8

Ok, consider the arguments:

• a function (which takes a list item and a value (a possible partial result) of the same type of return value);
• specification of the original result for a special case with an empty list
• list;

return value:

• some end result

First, he applies the function to the last item in the list and to the result of an empty list. Then he again uses the function with this result and the previous element, and so on, until he accepts some current result, and the first element of the list returns the final result.

Fold “folds” the list around the initial result, using a function that takes an element and some previous folding result. He repeats this for every element. So foldr does this, starting at the end of the list or on the right side.

folr f emptyresult [1,2,3,4] turns into f(1, f(2, f(3, f(4, emptyresult) ) ) ) . Now just follow the brackets in the assessment and what it is.

It is important to note that the supplied function f must treat its own return value as its second argument, which implies that both must be of the same type.

Source: my post where I look at it from the imperative unreasonable point of view of javascript if you think this can help.

Answer 9

I think that implementing map, foldl and foldr in a simple way helps explain how they work. The above examples also help in our understanding.

  myMap f [] = [] myMap f (x:xs) = fx : myMap f xs myFoldL fi [] = i myFoldL fi (x:xs) = myFoldL f (fix) xs > tail [1,2,3,4] ==> [2,3,4] > last [1,2,3,4] ==> 4 > head [1,2,3,4] ==> 1 > init [1,2,3,4] ==> [1,2,3] -- where f is a function, -- acc is an accumulator which is given initially -- l is a list. -- myFoldR' f acc [] = acc myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l) myFoldR fz [] = z myFoldR fz (x:xs) = fx (myFoldR fz xs) > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] > foldl (\xy -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 > myFoldL (\xy -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 foldl from above: Starting accumulator = 54 (12 + 54) / 2 = 33 (4 + 33) / 2 = 18.5 (10 + 18.5) / 2 = 14.25 (6 + 14.25) / 2 = 10.125` > foldr (++) "5" ["1", "2", "3", "4"] ==> "12345" > foldl (++) "5" ["1", "2", "3", "4"] ==> "51234" > foldr (\xy -> (x+y)/2) 54 [12,4,10,6] ==> 12 > myFoldR' (\xy -> (x+y)/2) 54 [12,4,10,6] ==> 12 > myFoldR (\xy -> (x+y)/2) 54 [12,4,10,6] ==> 12 foldr from above: Starting accumulator = 54 (6 + 54) / 2 = 30 (10 + 30) / 2 = 20 (4 + 20) / 2 = 12 (12 + 12) / 2 = 12