An abstraction for structural recursion
In the previous chapter, we studied recursive functions and presented structural recursion schemes as a useful template to write such functions. Thanks to HOF, we can capture these structural recursion schemes in reusable functions.
Folding lists
The first structural recursion scheme we encountered in the previous chapter is that for lists:
f :: [A] -> B f [] = n f (x:xs) = c x (f xs)
By replacing the underlined elements in the preceding template with concrete names, we obtain different functions, such as sum and and:
Prelude
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs
and :: [Bool] -> Bool
and [] = True
and (x:xs) = x && and xs Thanks to the ability to parameterize over functions, we can actually do better than this. Indeed, we can capture the recursion scheme in a HOF called foldr:
Prelude
foldr :: (a...