Understand Foldr Operator
I can not quite remember the usage of foldr until I finish the video by Erik Meijer on Chapter 71.
1. Descrption by Erik
Erik describe foldr in a very comprehensive way.
Take refining the length function in terms of foldr as a example.
length has a definition as
│ > length :: [a] -> Int │ > length [] = 0 │ > length (x:xs) = 1 + length xs
and
length [1,2,3]
= length (1:(2:(3:[])))
= 1 + (1 + (1 + 0))
= 3
By replace each (:) by \ _ n -> 1 + n and [] by 0, we have:
│ > length = foldr (\ _ n -> 1 + n) 0
2. Definition by Graham
Having such knowledge inside, I find Graham’s tutorial paper2 about fold again. There is a concise description of what fold is:
The function fold f v processes a list of type [a] to give a value of type b by replacing the nil constructor [] at the end of the list by the value v, and each cons constructor (:) within the list by the function f.
In Haskell, the fold operator can be defined as follows:
│ fold :: (a -> b -> b) -> b -> [a] -> b │ fold f v [] = v │ fold f v (x:xs) = f x (fold f v xs)
3. In one sentence
Thought it might not be that precisely.
│ foldr :: (a -> b -> b) -> b -> [a] -> b
Pull element one by one from right side of the list and apply the callback
│ foldl :: (a -> b -> a) -> a -> [b] -> a
Basically, pull element one by one from left side of the list and apply the callback