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.
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
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
* 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
insert, don't write any recursive functions.
Don't let the prelude do all the work. Avoid the
product, and append (
foldl to implement
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:
Now, using type-directed programming, write implementations.
Write a solver for Boolean formulas. Your solver should have
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
I suggest you use the method outlined by John Hughes in his paper Why Functional Programming Matters. We'll discuss other methods soon.