Case Distinctions

The final tool we often use in mathematics to define functions is case distinctions, something like:

\[f(x) = \begin{cases} 0 & \text{if } x = 0\\ 1 & \text{if } x = 1\\ f(x-1) + f(x-2) & \text{otherwise.} \end{cases}\]

or maybe

\[\begin{aligned} f(0) &= 0\\ f(1) &= 1\\ f(x) &= f(x-1) + f(x-2)\ \text{for}\ x > 1. \end{aligned}\]

Haskell offers various ways to express this type of case distinction, and we will discuss them all later. The formulation that matches the second form above most closely is

f :: Integer -> Integer
f 0 = 0
f 1 = 1
f x = f (x - 1) + f (x - 2)

The condition that the last equation applies only for values \(x > 1\) is implicit because Haskell uses pattern matching to find the first equation for f that applies to a given argument. When calling f with some argument y, then Haskell checks whether y is 0. If so, it uses the first equation to determine that f y = 0, and it ignores the other two equations. If y is 1, then the first equation does not match because y is not 0, but the second equation matches, and f y = 1. Finally, if y is not 0 nor 1, then the first two equations do not apply, so Haskell uses the third equation and calculates f x by calling f recursively with arguments x - 1 and x - 2 and adding the two results. You may have noticed that f n is simply the \(n\)th Fibonacci number.

And that's it. In math, we define functions directly if they are simple, by composing simpler functions to build more complex functions, and by using case distinctions to choose between different function values based on the argument value. It turns out that this is also all we need to program effectively and elegantly. The only caveat is that composing simpler functions to build more complex ones explicitly becomes tedious quickly, so Haskell offers useful syntax to express function composition more naturally. This gives us the ability to introduce local variables and refer to these local variables in our definitions of the final function value or of other local variables. This is analogous to using local variables in languages you are already familiar with. All of this is just "syntactic sugar", though, syntax meant to make programming easier. It would be entirely possible, but not particularly elegant, to write complex programs entirely without ever using a local variable and by specifying the program as the explicit composition of simpler functions.