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.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.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 (`++`

).

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

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