S02

Description

# Solutions to Exercises for November 9, 2018

Synopsis

## Exercise 3

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.

tail2 :: [a] -> [a] Source #

tail2 xs = tail (tail xs)

Since tail is of type [a] -> [a], the input xs as well as the result of tail2 both have to be lists with same element-type. Thus, tail2 is of type [a] -> [a].

triple :: Num a => a -> a Source #

triple x = x * 3

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

thrice :: (a -> a) -> a -> a Source #

thrice f x = f (f (f x))

Since f is applied to 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 thrice is (a -> a) -> a -> a.

mapPair :: (a -> b) -> (a, a) -> (b, b) Source #

mapPair f (x, y) = (f x, f y)

The function f is applied to both components x and y of the input pair. Thus, both have to be of the same type. Moreover, the output pair consists of two components that result from applying f. Again, this yields that both have to be of the same type. There are no further restrictions. In particular, there are not restrictions on f, except for it being a function. Hence, the type of f is a -> b. Taken together, this gives the type (a -> b) -> (a, a) -> (b, b) for mapPair.

idList :: [b] -> [b] Source #

idList = filter (const True)

The constructor True is of type Bool. Moreover, const is a function of type a -> b -> a. Consequently, const True is of type b -> Bool. Furthermore, filter has type (a -> Bool) -> [a] -> [a]. Which finally yields the type [b] -> [b] for idList.

## Exercise 4

Using the definition

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


The expression filter (const False) ["a","b","c"] can be evaluated as follows (where the justification for applying conditional equations resulting from guarded patterns are given on the right, separated by <==):

  filter (const False) ["a","b","c"]
= filter (const False) ["b","c"]   <== const False "a" /= True
= filter (const False) ["c"]       <== const False "b" /= True
= filter (const False) []          <== const False "c" /= True
= []


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


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


## Exercise 6

intercalate :: [a] -> [[a]] -> [a] Source #

Note the special treatment of singleton lists (that is, lists having exactly one element), which avoids the "separator" to be appended after the last list.