Assignments

Credits: these assignments are to quite some degree based on Karl-Filip Faxén's assignments for the similar reading course "Nonstrict Functional Programming Languages" at KTH/IT. Some assignments are fetched from Antony J. T. Davie: An Introduction to Functional Programming Systems Using Haskell, and Simon Thompson: Haskell: The Craft of Functional Programming.

Note that the assignments follow the order in Thompson's book only crudely. In particular, there are sometimes follow-up questions which request redoing an example using a more general technique which appears later in the book.

(Thompson 3.12) Define a function to convert small letters to capitals that returns unchanged characters which are not letters.

Thus, write a function to convert all small letters in a string to capitals! Write both a version that uses direct recursion, and a version that uses some appropriate higher-order function on lists (guess which...).

(Davie 2.3) Define a function to evaluate m over n = m!/n!(m-n)!, m >= n (binomial numbers):

Using the factorial function fact as a subsidiary.

Using the recurrence relation
- m over n = (m/n)(m-1 over n-1), for m >= n > 0
- m over 0 = 1, m >= 0

Using the recurrence relation
- m over n = (m-1 over n) + (m-1 over n-1), for m >= n > 0
- m over m = 1, for m >= 0

m over n

m-n over n

(Davie 3.15) Write a function that converts an integer to a string of digits representing it in an arbitrary number base.

(Davie 2.4) Define a function to calculate the square root of a number, to some given accuracy, using Newton-Raphson's method. For the square root function, this method replaces a guess x of the square root of a with 0.5*(x + a/x). Break the iteration when the difference between two successive iterates is less than the specified accuracy.

Now write a higher order function, which given a function f, its derivative f', initial guess, and accuracy, computes a numerical solution to the equation f(x) = 0 by the general version of Newton-Raphson's method, which computes a new guess x(n+1) from old guess x(n) according to x(n+1) = x(n) - f(x(n))/f'(x(n)).

Now abstract out the underlying computing structure even more: write a general, higher-order function for iterative algorithms that iterates a solution by applying a function until a convergence criterion is fulfilled. The convergence criterion should also be a parameter. Reimplement Newton-Raphson's method by calling this function with appropriate parameters.

(Thompson 5.13) Following the example in Thompson Ch. 5.6, define the functions borrowers, borrowed, and numBorrowed. Define each in the three following ways:
1. by direct recursion,
2. using list comprehensions (not numBorrowed), and
3. using higher-order functions on lists.

Give closed Haskell expressions e1, e2, e3 with the following most general types:
1. e1 :: a
2. e2 :: a -> b
3. e3 :: a -> a

Write a bignum package for arithmetics on arbitrary-sized integers by representing them as lists of fixed-size integers. (Do not use the built-in Integer data type!) Define a data type for your bignum's and make it an instance of the Num class. For the conversion function fromInteger, you can assume that your fixed-size integers are 32 bits long.

When you have done the above, write a new version of the fact function (p. 138 in Thompson's book) that uses your bignum's. How much new code do you have to write?

(Thompson 7.26) Design a function subst :: String -> String -> String -> String so that subst oldSub newSub st is the result of replacing the first occurrence in st of oldSub by the string newSub. If the substring oldSub does not occur in st, the result should be st.

(Thompson 8.2) Give a definition of a multiplication function mult :: Int -> Int -> Int such that mult 0 (fact (-2)) evaluates to 0 (where fact is the factorial function, with its "usual" recursive definition as on p. 138 in Thompson's book). What is mult (fact (-2)) 0? Explain why it is so.

Haskell is a lazy (or "call-by-need") language. There are other functional languages, such as ML and Scheme, which are eager (or "call-by-value"): in these languages, function arguments are always evaluated before the function is called. What would the result of a call to the equivalent of mult 0 (fact (-2)), but in an eager language, be?

(Davie 9.1, Thompson 8.4) Prove the associativity of the append operation ++ on lists (as defined on p. 122 in Thompson's book):
```
x ++ (y ++ z) = (x ++ y) ++ z
```
Hint: do not forget the case when some of the arguments are nonterminating!

Are the following two expressions equivalent? Motivate your answer!
1. foldr (\ x y -> f x + y) 0 xs
2. foldr ((+) . f) 0 xs

(Thompson 13.2) Do the following pairs of types unify? If so, give a most general unifier for them; if not, explain why they fail to unify.
1. Int -> b and a -> Bool
2. (Int,a,a) and (a,a,Bool)

(Davie 4.1) Infer the polymorphic types, disregarding class constaints, of the following functions:

last [x]         = x
last (x:y:ys)    = last (y:zs)

length []        = 0
length (x:xs)    = length xs + 1

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

sum              = foldl (+) 0

Infer the polymorphic type, with class constraints, of the function foo defined below:

foo x:xs y:ys z:zs | y < z     = x + foo xs ys zs
                   | y == z    = x + foo xs ys zs
                   | otherwise = foo xs ys zs
foo _ _ _ = 0

To further your understanding of types, explain why

let f g x = (g x, g [x])
    g y   = [y]
in f g 'a'

does not type check whereas

let f x = (g x, g [x])
    g y = [y]
in f 'a'

does.

Define a polymorphic algebraic data type for binary trees of some type a, where a binary tree either is an element of type a, or a root with two subtrees that are binary trees.

Now define functions over your data type that compute the following:
1. The number of leaves in a binary tree.
2. The depth of a binary tree.
3. A foldtree function that folds a binary tree with respect to a binary function of type a -> a -> a (e.g., sums all elements in a numerical binary tree).
4. Finds whether a given element appears in a binary tree.

Using the Haskell modules, define an ADT for multisets. Multisets are like sets, except that each element has a multiplicity, that is: the number of times (possibly zero) it occurs in the multiset. Multisets are often called "bags" which should give some additional intuition. The ADT should support the following operations:
1. test for empty multiset,
2. creation of singleton multiset,
3. multiplicity of given element,
4. removal of element (some number of it), and
5. sub-multiset relation (you should come up with some reasonable definition, and then implement it).
Provide at least two different implementations of your ADT!

(Davie 7.1) Write programs to generate the following infinite objects (in at least some case(s), use list comprehensions):
1. the negative integers,
2. the infinite list of powers of two,
3. the terms of the series which sums to e**x, viz: 1 + (x/1!) + (x**2/2!) + ...,
4. the terms of the partial sums of the previous series, so that the nth term in this new list is the sum of the first n terms of the first list,

(Davie 7.8) Write a function that takes a set (implemented as a list) and produces its power set -- the set of all its subsets. It should operate fairly on infinite lists, producing every finite subset in finite time.

Synchronous stream programming is an interesting application of lazy programming, where the synchronous, potentially infinite streams are modelled by lazy lists. Synchronous streams can be used to model hardware on a "functional box" level, where functional units are connected by synchronous channels. Define the following stream operations on lazy lists representing streams:
1. A delay operation, which shifts a stream backwards one step in time. In the resulting stream, the first element is then undefined.
2. A slowdown operation, which "stretches out" a stream by a factor n such that element i (starting with zero) in the input stream goes to element n*i in the output stream. The other elements in the output stream are undefined.
3. A "fixed function" operation, which applies a given "scalar" function to each element in a synchronous stream. (This one is easy!)

Systolic arrays are hardware structures which define (and can be defined by) systems of synchronous streams. An example of an algorithm which has a systolic hardware implementation is n-tap FIR filtering of a time sequence x with coefficients a(1),...,a(n), where an output sequence s is defined by

s(k) = sum(i=1,...,n) a(i)*x(k-i), k > n.

A classical systolic array for FIR filtering is shown below:

Here, the coefficients are stored one per cell. On each time cycle, data is shifted into the cells, a multiply and add is performed in each cell, and results are shifted out. The function of each cell is shown below:

If this array is fed with an input stream from the right, with a slowdown of two and a timing as in the figure above, and if a sequence of ("two-slowdowned") zeroes is fed from the left, then each successive value of the filtered sequence will successively computed by accumulating the terms in the respective sums on its way to the right. (Use a pen and paper to trace a few steps of the computation to convince yourself that this is indeed true.)

Now, the assignment: write a function fir that models a systolic array with the given architecture, which computes the FIR sequence from an input sequence! As arguments it should take a list of n coefficients and an input sequence. Also provide a straightforward Haskell implementation of the FIR function, and validate your systolic solution vs. this "specification" by a number of test runs.

Write a function that converts a function of type String -> String to a "unix filter" that reads a file (sequence of characters), applies the string transformation function, and outputs the result! Then use this function to convert your to-upper-case converter from assignment 1 into a "filter", which does the same on files.

The "do"-notation for monads is really syntactic sugar for the monadic operations >>= and >>. This sugar is (essentially) resolved as follows:
```
do e1 ; e2      = e1 >> e2
do p <- e1 ; e2 = e1 >>= \p -> e2
```
Apply this transformation to the example function on p. 393 in Thompson's book (the "important example"). Now explain why the "assignment" of identifiers in the do-notation is not the same as a destructive assignment of a program variable in an imperative language!

Create a version of the state monad in Chapter 18.9 (pp. 409-411) in Thompson's book, where the state is a store that holds a single integer. Write new versions of return, >>=, and extract if necessary. Write functions update and readstate that overwrite the stored integer and read it, respectively (what types should they have?). Then write a version of the factorial function that is purely functional from the outside but implemented with state, imperatively, internally!

(Davie 10.1) Carry out the transformations that reduce the comprehension

[ (n*n-n*m, 2*n*m, n*n+m*m) | n <- [2..100],
                              m <- [1..n-1],
                              gcd n m = 1,
                              odd (m+n)
]

to case-map-filter-form.

(Davie 10.5) Use Burstall-Darlington techniques to transform the following program into a more efficient form:
```
average x = sum x /length x

sum []    = 0
sum (h:t) = h + sum t

length []    = 0
length (_:t) = 1 + length t
```
Give an estimate of how much your transformation should improve the running time!

Björn Lisper
bjorn.lisper#mdh.se