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:
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.