CODEWITHSUNDEEP
haskellfold
Gallaoui
Gallaoui

Reputation: 511

foldr - further explanation and example with a map function

I've looked at different folds and folding in general as well as a few others and they explain it fairly well.

I'm still having trouble on how it would work in this case.

length :: [t] -> Int
length list = foldr (+) 0 (map (\x ->1) list)

Could someone go through that step by step and try to explain that to me.

And also how would foldl work as well.

Upvotes: 0

Views: 398

Answers (1)

Chad Gilbert
Chad Gilbert

Reputation: 36375

(map (\x ->1) list) takes the list and turns it into a list of 1 values:

(map (\x ->1) ["a", "b", "c"]) == [1, 1, 1]

Now, if you substitute that in the original foldr, it looks like this:

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

The starting point is 0 and the aggregation function is (+). As it steps through each element in the list, you are basically adding up all the 1 values, and that's how you end up returning the length.

foldr starts from the right and works back to the head of the list. foldl starts from the left and works through the list. Because the aggregation function is (+) :: Num a => a -> a -> a, the ordering of the left and right arguments in (+) is logically inconsequential (with the caveat that foldl has stack overflow problems with large lists because of lazy evaluation)

Upvotes: 4

Related Questions