Variants on structural recursion
Not all recursive functions can be written in a basic structurally recursive manner on an algebraic datatype. Here, we will review a range of common variations and extensions.
Primitive recursion
Structurally recursive functions only use the recursive occurrences of a datatype (e.g., the tail of a list or the subtrees of a tree) in recursive calls. Consider the following predefined function, which multiplies all the elements of a list:
Prelude
product :: [Integer] -> Integer
product [] = 1
product (x:xs) = x * product xs The body of the recursive case only uses the tail of the list, xs, in the recursive call product, xs. This is an essential part of structural recursion; the tail cannot be used in any other way.
Primitive recursive functions (also called paramorphisms) relax this condition; the recursive occurrences can be used in other ways. For example, the following function computes all the tails of...
