1. Following up on the class topic of type-directed programming, consider functions of these types:

`````` p :: forall a b . (a -> b) -> [a] -> [b]

q :: forall a . (a -> Bool) -> [a] -> [a]

r :: forall a . (a -> Bool) -> [a] -> Bool

u :: forall a b . b -> (a -> b -> b) -> [a] -> b
``````

Using the method of type-directed programming, write implementations of functions of these types. If two or more implementations are equally sensible, write them all. Come to class prepared to explain your ideas about what is and is not sensible.

2. Write `sublist :: (Eq a) => [a] -> [a] -> Bool`, which tells whether one list is a sublist of another:

`````` *Finger> sublist [1, 2, 3] [100, 1, 101, 2, 102, 3]
True
*Finger> sublist [1, 2, 3] [100, 1, 101, 2, 102, 4]
False
``````

The funny constraint `Eq a` means that `sublist` can be applied only to lists of elements on which the equality test `==` is defined.

3. Use `map`, `foldl`, and `foldr` to define these functions:

`````` maxl    :: (Ord a)      => [a] -> a   -- largest element of a nonempty list
gcdl    :: (Integral a) => [a] -> a   -- greatest common divisor of a nonempty
-- list of integers
sum     :: (Num a) => [a] -> a        -- sum of a nonempty list of numbers
product :: (Num a) => [a] -> a        -- product of a nonempty list of numbers
append  :: [a] -> [a] -> [a]          -- appends two lists
snoc    :: a -> [a] -> [a]            -- add an element to the *end* of a list
reverse :: [a] -> [a]                 -- reverse a (finite) list
sort    :: (Ord a) -> [a] -> [a]      -- insertion sort
``````

Notes:

• `gcd`, `+`, and `*` all have identities, but `max` does not. You can use the same techniqe for all.

• For insertion sort, use the following auxiliary function:

`````` insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y    = x : y : ys
| otherwise = y : insert x ys
``````
• Aside from `insert`, don't write any recursive functions. Use `map`, `foldl`, and `foldr`.

• Don't let the prelude do all the work. Avoid the built-in `sum`, `product`, and append (`++`).

4. Use `foldr` or `foldl` to implement `length`, `map`, `filter`, `any`, and `all`. (All these functions are defined in the Prelude, and the compiler defines them in terms of folds so that it can easily optimize using fusion.)

5. In a functional language, we can represent a set by its characteristic function, so "set of `a`" is represented by type `a -> Bool`. Using this representation, give the types of these values and operations:

• the empty set
• test to see if an element is in a set
• set union
• set intersection
• set difference

Now, using type-directed programming, write implementations.

6. Write a solver for Boolean formulas. Your solver should have type `Formula -> Data.Map Variable Bool`. If the value of a variable is irrelevant to a solution, then it need not appear in the map. For example, if the formula is

``````x \/ y
``````

then one possible solution is `singleton "x" True`, and we don't care what `y` is.

I suggest you use the method outlined by John Hughes in his paper Why Functional Programming Matters. We'll discuss other methods soon.

Back to list of assignments