This lab signals a shift from basic Haskell topics to ones more directly pertinent to the main goals of the course. Specifically, we will consider the terms of various languages to be constituted from structures corresponding to algebraic datatypes, and their (denotational) semantics will typically be given in terms of folds (or more complex but fold-like functions). As we will see, folds (and their duals, unfolds) can be derived automatically for a large class of algebraic datatypes, so the phenomenon is not limited to lists.

In this lab, we will be working with folds for lists (re-casting some functions from previous labs in these terms) and with “folds” for natural numbers, defined in the Peano style.

Recall the Haskell `Prelude`

function called `foldr`

:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

There are several ways to think of `foldr`

: one is that it follows
exactly the recursive structure of lists, replacing every “cons”
(`:`

) by a parameter function (`f`

) and every “nil”
(`[]`

) by a parameter *value* (`z`

). In particular,
therefore, it calls itself recursively on the tail of a cons-list, as this
is where the type definition for lists (and thus their structure) is recursive.

But another way to think of `foldr`

, perhaps more pragmatically,
is that it captures (in a higher-order, parametric fashion) the general
“template style” of function definition over lists which we
have been encouraging in lab. In this style, we write a function over lists,
possibly with other arguments, as a two-clause definition, with one clause handling
the nil case and the handling the cons case. In the cons case, we expect to see
the head and the tail (conventionally named `x`

and `xs`

)
used on the right-hand side, but with the tail specifically handled by
recursion:

myfun :: p -> q -> ... -> [a] -> b
myfun p q ... [] = ...?...
myfun p q ... (x:xs) = ... x ... (myfun p q ... xs)

The definition of `foldr`

can then be seen as “wrapping up”
the parts of a typical template-style definition, in that **the parameters of the
foldr will correspond to the parts of the template pattern that vary**,
namely the right-hand side of the nil clause and, in a sense, the right-hand side
of the cons clause.

`x`

and the
**Hint:** when you are defining a function as a fold, it often helps to write
out its function parameter (corresponding to the cons case, or for naturals to the
successor case) as a *lambda expression*. Of course, you might also use a helper
function or a “sub-definition” in terms of a `where`

clause,
but the lambda form is often shortest. In any case, remember that **the function
parameter takes as its arguments the head item (e.g., x) and
the recursive results**, oif the same type as the overall results of the
function.

You can use the following code from lecture as the basis for your natural number definitions (just cut and paste it into the top of your file):

data Nat = Zero | Succ Nat deriving (Show, Ord, Eq)
-- a fold for nats
foldn z s Zero = z
foldn z s (Succ n) = s (foldn z s n)
plus m = foldn m Succ
mult m = foldn Zero (plus m)
expt m = foldn (Succ Zero) (mult m)
-- conversion functions
int = foldn 0 (+1)
nat 0 = Zero
nat n = Succ (nat (n-1))
-- lifting allows you to test nat functions on ints
-- e.g.: lift2 mult 5 4 => 20
lift f n = int (f (nat n))
lift2 g n m = int (g (nat n) (nat m))

(The first two functions are re-visits from previous labs; you will want to open up your code from those labs to use as a guide for defining the functions in this new way.)

- Re-write the
`power`

function from the last lab as a fold(r) on lists; recall that it takes a list argument (only) and returns a list of lists, in a fashion similar to the power-set operation in set theory. - Re-write the
`transpose`

function from the last lab as a fold(r) over lists. Recall that transpose takes a list of lists as argument, treating it as a sort of 2-dimensional matrix of elements, and “reflects” it along the diagonal.**Hint**: you can use an infinitely repeated nil (`repeat []`

) in the base case to match any “row length” you need, if you use the right function parameter. - Write a function
`double`

,*as a*which will multiply a number by two. (In particular,`foldn`

on natural numbers,*don’t*use`mult`

or`plus`

.) - Write a function
`yell`

which will take a`Nat`

as argument and return a`String`

with as many “a”s as the`Nat`

and an exclamation point at the end. (Idea: this is the yell someone makes as they fall off a cliff of the given height; longer for taller heights, but always with a sudden ending!)`yell (nat 10) ==> "aaaaaaaaaa!"`

- Write two (predicate) functions,
`even`

and`odd`

, which will each take a`Nat`

and return a boolean, telling whether the number is even or odd. - Use this pairing trick to write a factorial function
`fact`

; think about (1) what pair-transform will get you what you want and (2) what pair you want to start off with. (Here you can of course use the`mult`

function on naturals.) - You can use a similar trick to write a Fibonacci function
`fibs`

which will return a list of the first n Fibonacci numbers, given a natural number n. Rather than a pair, you will want to use a list as the intermediary: write a function from lists to lists (of`Nats`

) which will add a new Fibonacci result to the front (*hint:*extract two values from the front of the list and put a third back on, then just start with a good initial list of values (i.e., enough to “get off the ground”).`fibs (nat 10) ==> [89,55,34,21,13,8,5,3,2,1,1,0]`

We can use a little “trick” to define more complex functions on
natural numbers using folds that produce *pairs*: this will allow us to
keep track of two values as we go along in the recursion. For example, we can
use this idea to define a squaring function via the notion that the i^{th}
square is the sum of the first i odd numbers: we define a “successor”
function `b`

(i.e., a parameter for the fold) which takes us from a pair
of an odd number and a square to the next odd number and square:

-- (1,0) --b--> (3,1) --b--> (5,4) --b--> (7,9) --b--> (9,16) --b--> ...
b (n,m) = (S (S n), plus n m)

Then we start off the recursion with the `Nat`

pair corresponding to
(1,0) and fold over a number argument, extracting the second half of the pair at
the end of the fold to return the final square result:

square = snd . foldn (S Z, Z) b
where b (n,m) = (S (S n), plus n m)