Structural recursion
You may have noticed that the recursive functions we have written so far in this section show a great deal of commonality. This is no coincidence, as they are, in fact, all based on the same recipe for writing recursive functions, known as structural recursion. Structurally recursive functions are sometimes also called catamorphisms.
Structural recursion on lists
Let us revisit two recursive functions on lists we wrote earlier and expose their common structure:
evenLength :: [a] -> Bool
evenLength [] = True
evenLength (x:xs) = not (evenLength xs)
Prelude
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs These two definitions follow a standard recursion scheme to define functions over a list:
f :: [A] -> B f [] = n f (x:xs) = c x (f xs)
It features two equations, one for the empty list pattern, [], and one for the non-empty list pattern, ...
