Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does foldr work?

Can anybody explain how does foldr work?

Take these examples:

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

I am confused about these executions. Any suggestions?

like image 464
dinsim Avatar asked Nov 18 '09 17:11

dinsim


People also ask

What does foldr function do?

To recap, with foldr , the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl , the function argument takes a default value, the first element of the list, and returns a new default value.

What does foldr return?

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.

What is foldr function in Haskell?

From HaskellWiki. The foldr function applies a function against an accumulator and each value of a Foldable structure from right to left, folding it to a single value. foldr is a method of the Foldable typeclass: foldr (++) [] [[0, 1], [2, 3], [4, 5]] -- returns [0, 1, 2, 3, 4, 5]

What does foldl and foldr do?

The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.


1 Answers

The easiest way to understand foldr is to rewrite the list you're folding over without the sugar.

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

now what foldr f x does is that it replaces each : with f in infix form 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 
like image 107
Tirpen Avatar answered Oct 07 '22 14:10

Tirpen