Solutions to the Problem Sheet for LI Functional Programming - Week 2

Polymorphism

1. Find out the types of the following functions. Decide if they are polymorphic.

   Function	Type	Polymorphic
   fst	(a, b) -> a	yes
   (++)	[a] -> [a] -> [a]	yes
   not	Bool -> Bool	no
   head	[a] -> a	yes
   tail	[a] -> [a]	yes
   id	a -> a	yes

2. Explain, in your own words, what the function zip does. In the expression zip ['x', 'y'] [False], what are the type variables a and b of zip :: [a] -> [b] -> [(a, b)] instantiated by?

   The function zip traverses the two lists simultaneously while returning the pairs of the elements it encounters in a new list. If the lists are not the same length, the result will have the length of the shorter list. In the example, we have a = Char and b = Bool.

3. Find a polymorphic function in the GHC standard library whose type contains 3 type variables or more.

   Examples are zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] and flip :: (a -> b -> c) -> b -> a -> c.

4. Read Section 3.7 of Programming in Haskell. Compare the types of the examples given there with the types ghci indicates.

   The only one which differs is length :: Foldable t => t a -> Int which is generalized from just the type [a] of lists to arbitrary members of the Foldable typeclass.

Types and Typeclasses

1. Run, and understand, the following examples

   Expression	Result	Explanation
   False == 'c'	Error	The left side has type Bool while the right has type Char
   False == True	False
   False == not	Error	The left side had type Bool while the right has type Bool -> Bool
   False == not True	True
   not == id	Error	No instance of Eq for Bool -> Bool
   [not] == [ (id :: Bool -> Bool) ]	Error	No instance of Eq for Bool -> Bool

2. On type classes

   1. Find all the basic instances of the type class Bounded that are defined in the GHC Prelude (the libraries that are loaded when starting ghci, without importing any additional libraries). Find out what minBound and maxBound are for each of the instances.

      Type	minBound	maxBound
      Word	0	18446744073709551615
      Ordering	LT	GT
      Int	-9223372036854775808	9223372036854775807
      Char	\NUL	'\1114111'
      Bool	False	True

   2. What type classes do the type classes Fractional, Floating, Integral extend? What functions to they provide?

      Typeclass	Extends	Provides
      Fractional	Num	(/) :: a -> a -> a
      		recip :: a -> a
      		fromRational :: Rational -> a
      Floating	Fractional	pi :: a
      		exp :: a -> a
      		log :: a -> a
      		...
      Integral	Real a, Enum a	quot :: a -> a -> a
      		rem :: a -> a -> a
      		div :: a -> a -> a
      		...

   3. Another type class:

      1. Which type class defines the function enumFromTo?

         Enum

      2. Evaluate enumFromTo on elements of each instance of that type class.

         Type	Expression	Result
         Word	enumFromTo (1 :: Word) 3	[1,2,3]
         Ordering	enumFromTo LT GT	[LT,EQ,GT]
         Integer	enumFromTo (-1 :: Integer) 2	[-1,0,1,2]
         Int	enumFromTo (3 :: Int) 5	[3,4,5]
         Char	enumFromTo 'c' 'g'	"cdefg"
         Bool	enumFromTo True False	[]
         ()	enumFromTo () ()	[()]
         Float	enumFromTo (1.5 :: Float) 2.5	[1.5,2.5]
         Double	enumFromTo (1.5 :: Double) 2.5	[1.5,2.5]

      3. Explain the different output between :type enumFromTo 4 8 and :type enumFromTo 4 (8 :: Int).

         The former gives enumFromTo 4 8 :: (Enum a, Num a) => [a] and we see that the type is still polymorphic, since the type of both 4 and 8 is ambiguous. The latter specifies that 8 :: Int so that Haskell instantiates the type varialbe a to Int.

Functions in Haskell

1. Using the functions removeLast and removeElem from Handout - Functions, write a function that removes both the first and the last element of a list.

   removeFirstAndLast :: [a] -> [a]
   removeFirstAndLast = reverse . tail . reverse . tail

2. Using guarded equations, write a function of type Int -> Int -> Bool that returns True if the first argument is greater than the second and less than twice the second.

   betweenNand2n :: Int -> Int -> Bool
   betweenNand2n k n | k > n && k < 2 * n = True
                     | otherwise          = False

3. Write a function to pair each element of a list with its index.

   withIndex :: [a] -> [(Int,a)]
   withIndex l = zip [0 .. length l - 1] l
   
   withIndex' :: [a] -> [(Int,a)]
   withIndex' l = [ (i, l !! i) | i <- [0 .. length l-1] ]

4. Write a function which returns the reverse of a list if its length is greater than 7. Now modify the function so that the cutoff length is a parameter.

   reverse7 :: [a] -> [a]
   reverse7 l = if (length l > 7) then reverse l else l
   
   reverse7guard :: [a] -> [a]
   reverse7guard l | length l > 7 = reverse l
                   | otherwise    = l
   
   reverseParam :: Int -> [a] -> [a]
   reverseParam n l | length l > n = reverse l
                    | otherwise    = l

5. Write a function orB :: Bool -> Bool -> Bool that returns True if at least one argument is True.

   orB :: Bool -> Bool -> Bool
   orB True True = True
   orB True False = True
   orB False True = True
   orB False False = False
   
   orB' :: Bool -> Bool -> Bool
   orB' True _ = True
   orB' _ True = True
   orB' _ _ = False

6. Write a function swap :: (a, b) -> (b, a) that swaps the elements of a pair.

   swap :: (a,b) -> (b,a)
   swap (x,y) = (y,x)

7. Define three variants of a function third :: [a] -> a that returns the third element in any list that contains at least this many elements, using

   1. head and tail

      thirdHeadTail :: [a] -> a
      thirdHeadTail = head . tail . tail

   2. list indexing !!

      thirdIndex :: [a] -> a
      thirdIndex l = l !! 2

   3. pattern matching

      thirdMatching :: [a] -> a
      thirdMatching (_:_:x:_) = x

8. Define a function safetail :: [a] -> [a] that behaves like tail except that it maps [] to [] (instead of throwing an error). Using tail and isEmpty :: [a] -> Bool. Define safetail using

   1. a conditional expression

      isEmpty :: [a] -> Bool
      isEmpty [] = True
      isEmpty _  = False
      
      safeTailCond :: [a] -> [a]
      safeTailCond l = if isEmpty l then [] else tail l

   2. guarded equations

      safeTailGuard :: [a] -> [a]
      sageTailGuard l | isEmpty l = []
                      | otherwise = tail l

   3. pattern matching

      safeTailMatch :: [a] -> [a]
      safeTailMatch [] = []
      safeTailMatch (_:xs) = xs