Marty Stumpf
7 Apr 2022
•
4 min read
This is the fourth of a series of articles that illustrates functional programming (FP) concepts. As you go through these articles with code examples in Haskell (a very popular FP language), you gain the grounding for picking up any FP language quickly. Why should you care about FP? See this post.
In the last post, we learned about the foldable typeclass, which provides the foldr
method. In this post, we'll learn what this method is with an example.
As mentioned in earlier posts, we can treat recursions as separate higher order functions known as recursion schemes. One type of recursion scheme is catamorphisms (or fold in Richard Bird and Philip Wadler’s Introduction to Functional Programming).
Because knowing how to use recursion schemes improves your coding ability! Consider this exercise: finding the minimum element of a list. In Haskell, without using fold, we would compare the elements of the list a one by one, keeping the minimum of the element, until we reach the end of the list. For example (interested readers can also see the OCaml version):
findMinInner :: Ord a => [a] -> a -> a
findMinInner [] curMin = curMin
findMinInner (hd : tl) curMin =
if hd < curMin
then findMinInner tl hd
else findMinInner tl curMin
findMin :: Ord a => [a] -> Maybe a
findMin [] = Nothing
findMin (hd:tl) = Just (findMinInner tl hd)
Using catamorphisms, we can find the minimum for an Int
list in two lines:
findMinFold :: [Int] -> Int
findMinFold l = foldr (\x y -> if x < y then x else y) maxBound l
Or, using the function min
in the prelude to replace the anonymous function and eta-reducing l
:
findMinFold :: [Int] -> Int
findMinFold = foldr min maxBound
Catamorphisms dramatically reduce the amount of code because foldr
does exactly what we want it to do for us: recurse down each element of the list.
Maybe
typefindMin
returns a Maybe a
. The Maybe a
type is used when a type can be Nothing
. It either returns Nothing
or the value. In this case, when the input list is empty, the minimum element is nothing. Running the code in GHCi gives:
*Main> findMin [9,2,3,1]
Just 1
*Main> findMin []
Nothing
Using Maybe
is not strictly necessary, Haskell's prelude (standard library) includes the minimum
function which throws an exception when an empty list is the input:
*Main> minimum []
*** Exception: Prelude.minimum: empty list
*Main> minimum [4,5,6,7,8]
4
findMinFold
, on the other hand, returns the base case when the input list is empty.
Going back to the above example, what’s going on in that one line?
First, let us look at findMinFold
's type from GHCi:
Prelude> :t findMinFold
findMinFold :: (Foldable t, Ord b, Bounded b) => t b -> b
findMinFold
takes a foldable type b
and returns a result of type b
. More specifically, it takes a [Int]
and returns an Int
.
We invoke foldr
in findMinFold
, which has the following type signature:
*Main> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
That is, foldr
takes 3 inputs:
a
and one of type b
, and returns a result of type b
.b
.a
.In findMinFold
, we've given foldr
2 inputs. The first is the function min
, of type:
Prelude> :t min
min :: Ord a => a -> a -> a
min
happens to have the second input type the same as the first, but bear in mind that it doesn't have to be as an input function to foldr
!
The second input is maxBound
, of type:
Prelude> :t maxBound
maxBound :: Bounded a => a
Int
is an instance of the Bounded
typeclass. In findMinFold
, maxBound
is thus of type Int
. Note that Integer
and Float
are not bounded!
foldr
recurses the function with the earlier result as an input. In this example, foldr
does the following:
maxBound
:fold_left min max_int [] => maxBound
min
of maxBound
and the element:foldr min maxBound [e1] => min e1 maxBound
min
takes the result of (min e2 maxBound)
as an input, and compare it with e1
:foldr min [e1,e2] maxBound => min e1 (min e2 maxBound)
(min e3 maxBound)
as an input to compare with e2
,
the result of which is then compared to e1
: foldr min maxBound [e1,e2,e3] => min e1 (min e2 (min e3 maxBound))
and so on...
We can generalize it to any function f
, with z
as the starting case and x
as the list input, the result is as in the prelude with f
as an infix operator:
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
foldl
works similarly, except that the list elements are the first input to the function, and the brackets are to the left:
foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
You can see from the above example that to find the minimum element of a list, we can use foldr
or foldl
, naturally with the min
function as the function input. But how do we choose the base case input?
The base case is what fold returns on an empty list input. When the input to findMinFold
is an empty list, the base case is returned. As you can see from GHCi, the maximum Int
on my system is 9223372036854775807
:
*Main> findMinFold []
9223372036854775807
Other examples are:
-- adding 0 and x returns x
sum :: (Foldable t, Num a) => t a -> a
sum = foldr (+) 0
-- multiplying 1 and x returns x
product :: (Foldable t, Num a) => t a -> a
product = foldr (*) 1
Because the base case to foldr
is only there to safe guard an empty input, when you can be sure that the input is not empty, the base case would not be necessary! Haskell provides such option. We’ll see this in the next post, along with more examples of folds!
Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.
See other articles by Marty
Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ
108 E 16th Street, New York, NY 10003
Join over 111,000 others and get access to exclusive content, job opportunities and more!