# Haskell/YAHT/Type basics/Solutions

## Contents

## Simple Types[edit]

`String`

or`[Char]`

- type error: lists are homogenous
`Num`

{a}`=> (a, Char)`

`Int`

- type error: cannot add values of different types

## Polymorphic Types[edit]

The types:

`(a,b) -> b`

`[a] -> a`

`[a] -> Bool`

`[a] -> a`

`[[a]] -> a`

## Type Classes[edit]

### Motivation[edit]

### Equality Testing[edit]

### The Num Class[edit]

### The Show Class[edit]

## Function Types[edit]

### Lambda Calculus[edit]

### Higher-Order Types[edit]

### That Pesky IO Type[edit]

### Explicit Type Declarations[edit]

### Functional Arguments[edit]

The types:

`a -> [a]`

. This function takes an element and returns the list containing only that element.`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.`(Num a) => a -> a`

. Since we apply`(+)`

to`a`

, it must be an instance of`Num`

.`a -> String`

, or`a -> [Char]`

. This ignores the first argument, so it can be any type.`(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`

.- 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. `(Num a) => a -> a`

. Again, since we apply`(+)`

, this must be an instance of`Num`

.

## Data Types[edit]

### Pairs[edit]

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[edit]

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[edit]

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[edit]

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

### Enumerated Sets[edit]

### The Unit type[edit]

## Continuation Passing Style[edit]

It mimicks neither exactly. It's 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) [3]) ==> 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