# Quiz (Week 2)

## 1 Typing

Assuming for the sake of simplicity
that all numeric literals are of type `Int`

,
What is the type of the following Haskell expressions?

### 1.1 Question 1

```
"hello world"
```

- ✗
`string`

- ✔
`[Char]`

- ✗
`char*`

- ✗
`[String]`

In Haskell, strings are actually just lists of characters, and
the names of types (like `Char`

) are always written with an initial
upper-case letter.

### 1.2 Question 2

(1, 'x', [True])

- ✗
`List`

- ✗
`(Int, Char, Bool)`

- ✗
`Tuple`

- ✔
`(Int, Char, [Bool])`

In Haskell, a tuple `(x,y)`

is typed
according to the following rule:

This can be read as `(x,y)`

is of type \((\tau_1, \tau_2)\) if `x`

is
of type \(\tau_1\) and `y`

is of type \(\tau_2\).

A similar rule exists for triples like
`(1,'x',[True])`

, and as `1`

is of type `Int`

,
`'x'`

is of type `Char`

, and `[True]`

is of type `[Bool]`

, we have
answer 4 as the only correct answer.

### 1.3 Question 3

["x":[]]

- ✗
`[[Char]]`

- ✔
`[[[Char]]]`

- ✗
`[Char]`

- ✗
`String`

Keeping in mind that `String`

is a synonym for `[Char]`

, we have
the type of cons (the `(:)`

operator) as:

(:) :: a -> [a] -> [a]

If we apply the first argument, `"x"`

:

("x":) :: [[Char]] -> [[Char]]

Then apply the second argument, `[]`

, and we have:

("x":[]) :: [[Char]]

Lastly, this list of list of characters is in turn put in a list, as it is surrounded by square brackets. So the answer is number 2, or a list of lists of lists of characters.

### 1.4 Question 4

map (\x -> x + 1)

- ✗
`[a] -> [b]`

- ✗
`Int -> Int`

- ✔
`[Int] -> [Int]`

- ✗
`(Int -> Int) -> [Int] -> [Int]`

- ✗Invalid, as not enough arguments are given to
`map`

.

It's worth noting that *all functions in Haskell accept one argument and
return one result*. Multi-argument functions are emulated by writing a
function that, given its first argument, returns a *function* that awaits
further arguments. This technique is called *currying*.

For example, the function `map`

has the following type:

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

This can be more explicitly expressed with the right-associated parentheses, as follows:

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

Given the argument function `(\x -> x + 1)`

, a
lambda expression of type `Int -> Int`

, `map`

shall return a function of type `[Int] -> [Int]`

,
or option 3.

## 2 Evaluation

Choose all expressions that are equivalent to the following expressions^{1}:

### 2.1 Question 5

3 : [40] ++ [50] ++ 5 : [60]

- ✔
`3 : [40] ++ ([50] ++ 5 : [60])`

- ✗
`3 : ([40] ++ [50] ++ 5) : [60]`

- ✔
`(3 : [40] ++ [50]) ++ (5 : [60])`

- ✔
`3 : ([40] ++ [50] ++ (5 : [60]))`

- ✔
`3 : [40, 50] ++ [5, 60]`

It's important to note that the `(++)`

operator is associative, that is:

(xs ++ ys) ++ zs == xs ++ (ys ++ zs)

This can be proven by induction on `xs`

, with the aid of some helper lemmas.
Because of this associativity, the placement of parentheses around `++`

-terms
is not important, which makes options 1,3 and 4 correct. In addition, option
5 is also correct as we know that `[40] ++ [50] = [40,50]`

and that `5 : [60] = [5,60]`

.

### 2.2 Question 6

map ($ 5) [(-),(+),(*)]

- ✗
`map (\f x -> f x 5) [(-),(+),(*)]`

- ✔
`map (\f x -> f 5 x) [(-),(+),(*)]`

- ✗
`[(- 5),(+ 5),(* 5)]`

- ✔
`[(5 -),(5 +),(5 *)]`

- ✗The expression is invalid.

The `($)`

operator is defined as follows:

($) : (a -> b) -> a -> b f $ x = f x

That is, it applies everything on the right as an argument to the function
given on the left. It is typically used to eliminate parentheses in Haskell
code, but can also be used in a section like this, where `($ 5)`

is equivalent to `\f -> f 5`

which is equivalent
to `\f x -> f 5 x`

by η-expansion. Thus option 2
is correct. Taking option 2 and evaluating it further, we will get the list:

[\x -> (-) 5 x, \x -> (+) 5 x, \x -> (*) 5 x]

Which is equivalent to the operator sections used in answer 4.
Answers 1 and 3 are incorrect as they flip the order of arguments used
for the function. Answer 3 is even more incorrect as `(- 5)`

will be
interpreted as a negative number, not an operator section, and thus produce
a type error.

### 2.3 Question 7

*Note*: The functions `ord`

and `chr`

are from `Data.Char`

.
They convert `Char`

values to/from
their ASCII (or unicode) numbers, respectively.
For these questions, the answers may have a more general
type than the original expression. So long as a given answer
has
equivalent behaviour *for the type of the original expression*, we
consider the answer to be equivalent.

let increment x = 1 + x in \xs -> map chr (map increment (map ord xs))

- ✔
`map chr . map (1+) . map ord`

- ✔
`map (chr . (1+) . ord)`

- ✔
`map succ`

- ✗
`map chr $ map (1+) $ map ord`

- ✔
`\xs -> map chr . map (1+) $ map ord xs`

The following bit of equational reasoning hits every answer in this question, except 4, which is not type correct.

let increment x = 1 + x in \xs -> map chr (map increment (map ord xs)) = -- Shift argument into lambda let increment = \x -> 1 + x in \xs -> map chr (map increment (map ord xs)) = -- Simplify lambda to operator section let increment = (1 +) in \xs -> map chr (map increment (map ord xs)) = -- Reduce let expression by substitution \xs -> map chr (map (1 +) (map ord xs)) = -- Introduce composition, f (g x) = (f . g) x \xs -> (map chr . map (1 +)) (map ord xs)) = -- Remove parentheses with ($) \xs -> map chr . map (1 +) $ map ord xs -- Answer 5 = -- Introduce further composition: f $ g x = (f . g) x \xs -> (map chr . map (1 +) . map ord) xs = -- η-reduction map chr . map (1 +) . map ord -- Answer 1 = -- Map (functor) law, map f . map g = map (f . g) map (chr . (1 +) . ord) -- Answer 2 = -- succ is defined for Char values as chr . (1 +) . ord map succ -- Answer 3

### 2.4 Question 8

foldr (&&) True . map (>= 0)

- ✔
`and . map (>= 0)`

- ✔
`all (>= 0)`

- ✗
`any (>= 0)`

- ✔
`foldr (\a b -> a >= 0 && b) True`

- ✗
`foldl (\a b -> a && b > 0) True`

The following derivation shows the equivalence to answers 1 and 2.

foldr (&&) True . map (>=0) = -- and = foldr (&&) True and . map (>=0) -- Answer 1 = -- all f = and . map f all (>=0) -- Answer 2

Furthermore, Answer 4 is also equivalent, as the following derivation shows:

foldr (&&) True . map (>=0) = -- η-expansion on the (&&) foldr (\a b -> a && b) True . map (>=0) = -- We have a fold/map rule -- foldr (\x y -> z) . map f = foldr (\x y -> z[x := f x]) -- (where z[x:=f x] is a substitution). foldr (\a b -> (>= 0) a && b) True = -- Nicer syntax foldr (\a b -> a >= 0 && b) True -- Answer 4

## Footnotes:

^{1}

: By "equivalent", we mean will evaluate to equal results. We consider two functions equal if, for any input, they produce equal outputs (functional extensionality).