S02

Contents

Synopsis

Exercise 3

second :: [a] -> aSource

 second xs = head (tail xs)

Since tail is of type [a] -> [a], xs has to be of type [a] and thus tail xs is of type [a]. Combining this with the type of head (which is [a] -> a), we obtain a for head (tail xs) and thus [a] -> a for second.

swap :: (a, b) -> (b, a)Source

 swap (x,y) = (y,x)

Since there are no restrictions on x and y, the input of swap is an arbitrary tuple of type (a,b). Swapping the components then yields (b,a) and thus (a,b) -> (b,a) for swap.

pair :: a -> b -> (a, b)Source

 pair x y = (x,y)

Since there are no restrictions on x and y, the input of pair are two arbitrary values of types a and b. Constructing a pair out of those values, results in the type (a, b) and thus a -> b -> (a,b) for pair.

double :: Num a => a -> aSource

 double x = x*2

The operation (*) is of type Num a => a -> a -> a, hence x, needs to be of some Num-type, resulting in Num a => a -> a for double.

palindrome :: Eq a => [a] -> BoolSource

 palindrome xs = Prelude.reverse xs == xs

reverse is of type [a] -> [a] and has no class constraints. On the contrary, (==) is only applicable for types of the Eq class. Putting this together results in Eq a => [a] -> Bool for palindrome.

twice :: (a -> a) -> a -> aSource

 twice f x = f (f x)

Since f is applied on the result of f x, the input as well as the output of f need to be of the same type as x. There are no further restrictions. Hence the type of twice is (a -> a) -> a -> a.

Exercise 4

Using the definition

   map f [] = []
   map f (x:xs) = f x : map f xs

The expression map (+1) [1,2,3] can be evaluated as follows:

   map (+1) [1,2,3]
     = (1+1) : map (+1) [2,3] 
     = (1+1) : (2+1) : map (+1) [3]
     = (1+1) : (2+1) : (3+1) : map (+1) []
     = (1+1) : (2+1) : (3+1) : []
     = [2,3,4]

Exercise 5

reverse :: [a] -> [a]Source

For reverse we use the auxiliary function snoc ('cons' spelled backwards), which adds an element at the end of a list. Then, using foldr, we obtain

reverse = foldr snoc []

map :: (a -> b) -> [a] -> [b]Source

For map we use 'function composition' (.) (where (f . g) x = f (g x), reading 'first apply g and then apply f to the result') together with the 'cons' function (:). Using foldr, we obtain

map f = foldr ((:) . f) []

Exercise 6

concat :: [[a]] -> [a]Source

One possible definition is

concat []     = []
concat (x:xs) = x ++ concat xs

Again, we could use foldr to obtain the shorter definition

concat = foldr (++) []