Assignment 2 – Monads and Applicatives

The GitHub Classrooms link for this assignment is here.

The deadline for the assignment is 2025-02-22 @ 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, if these exist:

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]