# Yet Another Haskell Tutorial/Type basics/Solutions Preamble
Introduction
Getting Started
Language Basics (Solutions)
Type Basics (Solutions)
IO (Solutions)
Modules (Solutions)
Recursion
Complexity

## Simple Types

1. `String` or `[Char]`
2. type error: lists are homogenous
3. `Num`{a} `=> (a, Char)`
4. `Int`
5. type error: cannot add values of different types

## Polymorphic Types

The types:

1. `(a,b) -> b`
2. `[a] -> a`
3. `[a] -> Bool`
4. `[a] -> a`
5. `[[a]] -> a`

## Function Types

### Functional Arguments

The types:

1. `a -> [a]`. This function takes an element and returns the list containing only that element.
2. `a -> b -> b -> (a,[b])`. The second and third argument must be of the same type, since they go into the same list. The first element can be of any type.
3. `(Num a) => a -> a`. Since we apply `(+)` to `a`, it must be an instance of `Num`.
4. `a -> String`, or `a -> [Char]`. This ignores the first argument, so it can be any type.
5. `(Char -> a) -> a`. In this expression, `x` must be a function which takes a `Char` as an argument. We don't know anything about what it produces, though, so we call it `a`.
6. Type error. Here, we assume `x` has type `a`. But `x` is applied to itself, so it must have type `b -> c`. But then it must have type `(b -> c) -> c`, but then it must have type `((b -> c) -> c) -> c` and so on, leading to an infinite type.
7. `(Num a) => a -> a`. Again, since we apply `(+)`, this must be an instance of `Num`.

## Data Types

### Pairs

The definitions will be something like:

```data Triple a b c = Triple a b c

tripleFst (Triple x y z) = x
tripleSnd (Triple x y z) = y
tripleThr (Triple x y z) = z

```

The code, with type signatures, is:

```data Quadruple a b = Quadruple a a b b

firstTwo :: Quadruple a b -> [a]
firstTwo (Quadruple x y z t) = [x,y]

lastTwo :: Quadruple a b -> [b]
lastTwo (Quadruple x y z t) = [z,t]
```

We note here that there are only two type variables, `a` and `b` associated with `Quadruple`.

### Multiple Constructors

The code:

```data Tuple a b c d = One a
| Two a b
| Three a b c
| Four a b c d

tuple1 (One   a      ) = Just a
tuple1 (Two   a b    ) = Just a
tuple1 (Three a b c  ) = Just a
tuple1 (Four  a b c d) = Just a

tuple2 (One   a      ) = Nothing
tuple2 (Two   a b    ) = Just b
tuple2 (Three a b c  ) = Just b
tuple2 (Four  a b c d) = Just b

tuple3 (One   a      ) = Nothing
tuple3 (Two   a b    ) = Nothing
tuple3 (Three a b c  ) = Just c
tuple3 (Four  a b c d) = Just c

tuple4 (One   a      ) = Nothing
tuple4 (Two   a b    ) = Nothing
tuple4 (Three a b c  ) = Nothing
tuple4 (Four  a b c d) = Just d

```

The code:

```fromTuple :: Tuple a b c d -> Either (Either a (a,b)) (Either (a,b,c) (a,b,c,d))
fromTuple (One   a      ) = Left  (Left  a        )
fromTuple (Two   a b    ) = Left  (Right (a,b)    )
fromTuple (Three a b c  ) = Right (Left  (a,b,c)  )
fromTuple (Four  a b c d) = Right (Right (a,b,c,d))
```

Here, we use embedded `Either`s to represent the fact that there are four (instead of two) options.

### Recursive Datatypes

The code:

```listHead (Cons x xs) = x
listTail (Cons x xs) = xs

listFoldl f y Nil = y
listFoldl f y (Cons x xs) = listFoldl f (f y x) xs

listFoldr f y Nil = y
listFoldr f y (Cons x xs) = f x (listFoldr f y xs)

```

### Binary Trees

The code:

```elements (Leaf x) = [x]
elements (Branch lhs x rhs) =
elements lhs ++ [x] ++ elements rhs

```

The code:

```
treeFoldr :: (a -> b -> b) -> b -> BinaryTree a -> b
treeFoldr f i (Leaf x) = f x i
treeFoldr f i (Branch left x right) = treeFoldr f (f x (treeFoldr f i right)) left

elements2 = treeFoldr (:) []
```

or:

```elements2 tree = treeFoldr (\a b -> a:b) [] tree
```

The first `elements2` is simply a more compact version of the second.

The code:

```treeFoldl :: (a -> b -> a) -> a -> BinaryTree b -> a
treeFoldl f i (Leaf x) = f i x
treeFoldl f i (Branch left x right) = treeFoldl f (f (treeFoldl f i left) x) right

elements3 t = treeFoldl (\i a -> i ++ [a]) [] t
```

## Continuation Passing Style

It mimicks neither exactly. Its behavior most closely resembles `foldr`, but differs slightly in its treatment of the initial value. We can observe the difference in an interpreter:

Example:

```CPS> foldr (-) 0 [1,2,3]
2
CPS> foldl (-) 0 [1,2,3]
-6
CPS> fold  (-) 0 [1,2,3]
-2
```

Clearly it behaves differently. By writing down the derivations of `fold` and `foldr` we can see exactly where they diverge:

```     foldr (-) 0 [1,2,3]
==>  1 - foldr (-) 0 [2,3]
==>  ...
==>  1 - (2 - (3 - foldr (-) 0 []))
==>  1 - (2 - (3 - 0))
==>  2

fold  (-) 0 [1,2,3]
==>  fold' (-) (\y -> 0 - y) [1,2,3]
==>  0 - fold' (-) (\y -> 1 - y) [2,3]
==>  0 - (1 - fold' (-) (\y -> 2 - y) )
==>  0 - (1 - (2 - 3))
==>  -2
```

Essentially, the primary difference is that in the `foldr` case, the "initial value" is used at the end (replacing `[]`), whereas in the CPS case, the initial value is used at the beginning.

The function `map` in CPS:

```map' :: (a -> [b] -> [b]) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = f x  (map' f xs)

map2 :: (a -> b) -> [a] -> [b]
map2 f l = map' (\x y -> f x : y) l
```

Point elimination:

```map2 f = map' (\x y -> (:) (f x) y)
map2 f = map' (\x -> (:) (f x))
map2 f = map' (\x -> ((:) . f) x)
map2 f = map' ((:) . f)
```

The function `filter` in CPS: (needs to be double checked)

```filter' :: (a -> [b] -> [b]) -> [a] -> [b]
filter' f [] = []
filter' f (x:xs) = f x  (filter' f xs)

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 f l = filter' (\x y -> if (f x) then x:y else y) l
```