S02

Synopsis

# Exercise 3

second :: [a] -> a Source #

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 -> a Source #

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] -> Bool Source #

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 -> a Source #

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

  filter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs


The expression filter (== 3) [1,2,3] can be evaluated as follows (where the justification for applying conditional equations resulting from guarded patterns are given on the right, separated by <==):

  filter (== 3) [1,2,3]
= filter (== 3) [2,3]   <== 1 /= 3
= filter (== 3) [3]     <== 2 /= 3
= 3 : filter (== 3) []  <== 3 == 3
= 3 : []
= [3]


# 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 (++) []