CS 465 Lab 3: Folds for lists and naturals

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.

Fold functions

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.

Definitions for Peano-style natural numbers

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 exercises

(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.)

  1. 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.
  2. 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.
  3. Write a function double, as a foldn on natural numbers, which will multiply a number by two. (In particular, don’t use mult or plus.)
  4. 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!"
  5. 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.

  6. 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)


  7. 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.)
  8. 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]