REVISED: Friday, February 9, 2024
Haskell foldr.
I. HASKELL FOLDR
foldr simultaneously replaces each (:) in a list by a given function, and [] by a given value:
sum = foldr (+) 0
product = foldr (*) 1
or = foldr (||) False
and = foldr (&&) True
A. HASKELL FOLDR EXAMPLES
1. Generic Haskell foldr
foldr :: (a -> a -> a) -> a -> [a] -> a
foldr f a [] = a
foldr f a (x:xs) = f x (foldr f a xs)
Prelude> foldr (+) 50 [10,20,30,40]
150
it :: Num a => a
Prelude>
foldr begins at the right-hand end of the list and combines each list entry with the accumulator value using the function you give it. The result is the final value of the accumulator after "folding" in all the list elements.
(10 + (20 + (30 + (40 + 50))))
The above is the same as:
40 + 50 = 90
30 + 90 = 120
20 + 120 = 140
10 + 140 = 150
2. Haskell foldr sum
mysum :: [Int] -> Int
mysum xs = (foldr add) (0 xs) -- 0 is the sum identity for [].
where
add x y = x + y
mysum [1,2,3,4]
=
foldr add 0 [1,2,3,4]
=
(add 1 (add 2 (add 3 (add 4 0))))
=
(1 + (2 + (3 + (4 + 0))))
=
10
Prelude> :load mysum
[1 of 1] Compiling Main ( mysum.hs, interpreted )
Ok, modules loaded: Main.
[1 of 1] Compiling Main ( mysum.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Prelude> mysum [1,2,3,4] -- Prelude has a sum function.
10
Prelude> mysum [1,2,3,4] -- Prelude has a sum function.
10
Prelude>
4 + 0 = 4
3 + 4 = 7
2 + 7 = 9
1 + 9 = 10
3. Haskell foldr product
product :: [Int] -> Int
product xs = foldr times 1 xs -- 1 is product identity for [].
where
times x y = x * y
4. Haskell foldr concat
concat :: [[a]] -> [a]
concat xs = foldr append [] xs -- empty list [] for append.
where
append xs ys = xs ++ ys
5. Haskell map filter and foldr sum of squares of positives
"Copy Paste" the following function into your text editor and "File, Save As" f5.hs to your working directory:
f5 :: [Int] -> Int
f5 xs = foldr add 0 (map square (filter positive xs))
where
add x y = x + y
square x = x * x
positive x = x > 0
Load the above function into GHCi as follows:
Prelude> :load f5
[1 of 1] Compiling Main ( f5.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Prelude> :type f5
f :: [Int] -> Int
Prelude>
From GHCi call function f5 as follows:
Prelude> f5 [1,-2,3,-4]
10
it :: Int
Prelude>
-4 > 0 = False
3 > 0 = True 3 ^ 2 = 9
-2 > 0 = False
1 > 0 = True 1 ^ 2 = 1
9 + 0 = 9
1 + 9 = 10
Think of foldr non-recursively as simultaneously replacing each (:) in a list by a given function, and [] by a given value. In other words, for each constructor it applies a certain function.
Given := is read as, "is replaced by."
xs [ (:) := f, [] := v]
For example:
{-
Replace each (:) with (+) and [] with 0.
sum [4,5,6]
=
foldr (+) 0 [4,5,6]
=
-- foldr (+) 0 (4:(5:(6:[])))
-- =
4+(5+(6+0))
=
15
-}
As shown below, the choice between foldr and foldl could make a difference:
Prelude> foldr (div) 70 [340,560,120,40,230]
5
Prelude>
Prelude> (340 / (560 / (120 / (40 / (230 / 70)))))
5.9846938775510194
Prelude>
Prelude> foldl (div) 70 [340,560,120,40,230]
0
Prelude>
Prelude> (((((340/70)/560)/120)/40)/230)
7.856403430937593e-9
Prelude>
6. REVERSE
Prelude> let reverse = foldr (\x -> \xs -> xs ++ [x]) []
Prelude>
Prelude> :type reverse
reverse :: [a] -> [a]
Prelude>
Prelude> reverse [1,2,3]
[3,2,1]
Prelude>
7. FACTORIAL
fac :: (Num b, Enum b) => b -> b
fac n = foldr (*) 1 [1..n]
Prelude> :load fac
[1 of 1] Compiling Main ( fac.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Prelude> fac 3
6
Prelude>
(1 * (2 * (3 * 1)))
The above is the same as:
3 * 1 = 3
2 * 3 = 6
1 * 6 = 6
As shown below, the choice between foldr and foldl could make a difference:
Prelude> foldr (div) 70 [340,560,120,40,230]
5
Prelude>
Prelude> (340 / (560 / (120 / (40 / (230 / 70)))))
5.9846938775510194
Prelude>
Prelude> foldl (div) 70 [340,560,120,40,230]
0
Prelude>
Prelude> (((((340/70)/560)/120)/40)/230)
7.856403430937593e-9
Prelude>
6. REVERSE
Prelude> let reverse = foldr (\x -> \xs -> xs ++ [x]) []
Prelude>
Prelude> :type reverse
reverse :: [a] -> [a]
Prelude>
Prelude> reverse [1,2,3]
[3,2,1]
Prelude>
7. FACTORIAL
fac :: (Num b, Enum b) => b -> b
fac n = foldr (*) 1 [1..n]
Prelude> :load fac
[1 of 1] Compiling Main ( fac.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Prelude> fac 3
6
Prelude>
(1 * (2 * (3 * 1)))
The above is the same as:
3 * 1 = 3
2 * 3 = 6
1 * 6 = 6
II. CONCLUSION
In this tutorial, you have been introduced to some of the advantages and disadvantages of using Haskell foldr.
III. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
