Haskell finger exercises

  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]
     *Finger> sublist [1, 2, 3] [100, 1, 101, 2, 102, 4]

    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


  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:

  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