# Recursion Principles and Foldables

Consider the definition of the simplest foldable data structure: the Natural Number!

``````data Nat = Zero

-- How to print natural numbers a nice way :P
instance Show Nat where
show Zero     = show (0 :: Integer)
show (Add1 n) = show \$ 1 + (read \$ show n)
``````

A natural number is either `Zero` or the successor of (i.e., 1 value greater than) another natural number. Think peano numbers. With this, we have defined a data structure that includes all positive integers and as well as 0.

Let’s define some basic functions for Natural Numbers:

``````-- add two natural numbers together.
plus :: Nat -> Nat -> Nat
plus Zero     y = y

-- multiply two natural numbers.
times :: Nat -> Nat -> Nat
times Zero     _ = Zero
times (Add1 x) y = (x `times` y) `plus` y

-- pow raises its first argument to the power of the second argument.
pow :: Nat -> Nat -> Nat
pow _ Zero     = Add1 Zero
pow x (Add1 y) = (x `pow` y) `times` x
``````

Cool, but nothing really out of the ordinary here. These are just your average, every-day run of the mill recursively defined functions, but we can make things a bit more interesting.

Consider the following definition of `foldNat`, which behaves exactly like a reducer (i.e., a recursion principle) for natural numbers.

Any data structure that is defined similarly to natural numbers (e.g. Lists) has a corresponding `fold` function. Looking at its type definition, `foldNat` takes an `a`, a function of type `a -> a`, a `Nat` and returns an `a`. One should think of `a` as equivalent to any type, which makes `foldNat` an example of a polymorphic function. I will write more about those later on :)

Essentially, the job of `foldNat` is to take any natural number into the appropriate `a`. For example, reading the first line of `foldNat` says that:

In the event that `n` is the natural number `Zero`, `foldNat` should return `base`.

Consequently, the second line of `foldNat` is called in the event that the given `n` is not `Zero` but is instead the `Add1` of another natural number `n`. Thus, `foldNat` would then recur on the smaller natural number, `n`, resulting in an `a` which is then passed to `recur` that does whatever it is it’s meant to do. The real magic that happens is mostly contained within the function `recur` passed to `foldNat` (hint hint).

``````foldNat :: a -> (a -> a) -> Nat -> a
foldNat base recur Zero     = base
foldNat base recur (Add1 n) = recur \$ foldNat base recur n
``````

To further understand what exactly `foldNat` is meant to do, I’ve included some exercises! As an example, I’ve done the first of these.

For those who want a little bit more, I’ve also included a bonus question to define factorial (`fact`) in terms of `foldNat`.

Good luck!

Hint: You may find it useful to define a few natural numbers to avoid having to write out a long series of `Add1`s every time you want to test your functions. For example:

``````two :: Nat

five :: Nat
``````

Exercises:

``````-- 1. Define `plusFold` that behaves like `plus` but uses `foldNat`.
plusFold :: Nat -> Nat -> Nat
plusFold m n = foldNat n Add1 m

-- 2. Define `timesFold` that behaves like `times` but uses `foldNat`.
timesFold :: Nat -> Nat -> Nat
timesFold = undefined

-- 3. Define `powFold` that behaves like `pow` but uses `foldNat`.
powFold :: Nat -> Nat -> Nat
powFold = undefined

-- BONUS!! This is rather difficult...
fact :: Nat -> Nat