Skip to main content

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

FunctionTypePolymorphic
fst(a, b) -> ayes
(++)[a] -> [a] -> [a]yes
notBool -> Boolno
head[a] -> ayes
tail[a] -> [a]yes
ida -> ayes
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

ExpressionResultExplanation
False == 'c'ErrorThe left side has type Bool while the right has type Char
False == TrueFalse
False == notErrorThe left side had type Bool while the right has type Bool -> Bool
False == not TrueTrue
not == idErrorNo instance of Eq for Bool -> Bool
[not] == [ (id :: Bool -> Bool) ]ErrorNo 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.

TypeminBoundmaxBound
Word018446744073709551615
OrderingLTGT
Int-92233720368547758089223372036854775807
Char\NUL'\1114111'
BoolFalseTrue
2. What type classes do the type classes Fractional, Floating, Integral extend? What functions to they provide?

TypeclassExtendsProvides
FractionalNum(/) :: a -> a -> a
recip :: a -> a
fromRational :: Rational -> a
FloatingFractionalpi :: a
exp :: a -> a
log :: a -> a
...
IntegralReal a, Enum aquot :: 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.

TypeExpressionResult
WordenumFromTo (1 :: Word) 3[1,2,3]
OrderingenumFromTo LT GT[LT,EQ,GT]
IntegerenumFromTo (-1 :: Integer) 2[-1,0,1,2]
IntenumFromTo (3 :: Int) 5[3,4,5]
CharenumFromTo 'c' 'g'"cdefg"
BoolenumFromTo True False[]
()enumFromTo () ()[()]
FloatenumFromTo (1.5 :: Float) 2.5[1.5,2.5]
DoubleenumFromTo (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 -> BoolbetweenNand2n 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] lwithIndex' :: [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 lreverse7guard :: [a] -> [a]reverse7guard l | length l > 7 = reverse l                | otherwise    = lreverseParam :: 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 -> BoolorB True True = TrueorB True False = TrueorB False True = TrueorB False False = FalseorB' :: Bool -> Bool -> BoolorB' True _ = TrueorB' _ True = TrueorB' _ _ = 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] -> athirdHeadTail = head . tail . tail
2. list indexing !!

thirdIndex :: [a] -> athirdIndex l = l !! 2
3. pattern matching

thirdMatching :: [a] -> athirdMatching (_:_: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] -> BoolisEmpty [] = TrueisEmpty _  = FalsesafeTailCond :: [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