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

data Nat = Zero
         | Add1 Nat

-- 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
plus (Add1 x) y = Add1 (x `plus` 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 Add1s every time you want to test your functions. For example:

two :: Nat
two = Add1 (Add1 Zero)

five :: Nat
five = Add1 (Add1 (Add1 (Add1 (Add1 Zero))))

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
fact Zero     = Add1 Zero
fact (Add1 n) = (Add1 n) `times` (fact n)

factFold :: Nat -> Nat
factFold = undefined