Summary

This chapter introduced the concept of recursive definitions for both functions and datatypes. We saw how recursive datatypes allow us to express values of an arbitrarily large size, with Haskell’s built-in list type as a notable example. Functions that process such recursive datatypes are themselves naturally recursive. More specifically, when the recursive structure of a function aligns with that of the datatype it processes, we speak of structural recursion. We saw several common variations in structural recursion as well as a few examples of non-structural recursion.

In Chapter 4, Higher-Order Functions, we will see how repeated patterns in function definitions, such as the structural recursion scheme we used here, can themselves be captured as reusable code. The key mechanism that enables this is the ability to pass functions as parameters to other functions. Such functions with function parameters are called higher-order functions.