# Assignment 2 – Monads and Applicatives

The GitHub Classrooms link for this assignment is here

The deadline for the assignment is 2023-02-22 @ 23:59. The deadline for the reviews of this assignment is 2023-03-01 @ 23:59.

#### Grading

- Each requested instance is worth half a point. Since there are 5 classes times 3 types = 15 instances, the first two sections are 7,5 points in total.
- The exercise with
`lookup`

is worth 1,5 points. - The exercise with
`foldMap`

is worth 1 point.

## Functors, applicative and monad

Given the standard type classes for functors, applicative functors and monads:

```
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
class Applicative f => Monad f where
return :: a -> f a
(>>=) :: f a -> (a -> f b) -> f b
```

Give instances for all three classes for the following data types:

```
data Tree a = Leaf a | Node (Tree a) (Tree a)
data RoseTree a = RoseNode a [RoseTree a] | RoseLeaf
data Teletype a = Get (Char -> Teletype a)
| Put Char (Teletype a)
| Return a
```

## Foldable & traversable

Also give instances for the `Foldable`

and `Traversable`

classes:

```
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
class Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
```

## Maps and keys

Using only methods from the above type classes and `lookup`

, show how to
define the following function:

```
lookupAll :: Ord k => [k] -> Data.Map k v -> Maybe [v]
```

This should return `Just vs`

if all the argument keys occur in the
map, and `Nothing`

otherwise.

Also define the following variant:

```
lookupSome :: Ord k => [k] -> Data.Map k v -> [v]
```

that returns the list of values for which a key exists. You may want
to use functions from `Data.Maybe`

to complete this definition.

## Filter

Use `foldMap`

to define a generic filter function:

```
gfilter :: Foldable f => (a -> Bool) -> f a -> [a]
```