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