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. But, for the cons case, the right-hand side will in
general depend somehow on the values of the head item x and the
recursive result of the call to the defined function. So, for this clause
the parameter we pass in is a function of those parts of the usual template-style
right-hand side.
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.)
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.
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.
double, as a foldn on
natural numbers, which will multiply a number by two. (In particular,
don’t use mult or plus.)
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!"
even and odd,
which will each take a Nat and return a boolean, telling
whether the number is even or odd.
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 ith
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)
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.)
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]