Exercises to familiarize yourself with many standard typeclasses

FunctionalAbstractions.lhs

We are going to be redefining a bunch of things that are in prelude in order to
make them explicit and all in one place:

> {-# LANGUAGE NoImplicitPrelude #-}

It is best for learning to be able to write concretized signatures of typeclass
functions when defining instances:

> {-# LANGUAGE InstanceSigs #-}

We're going to have a couple empty types, so:

> {-# LANGUAGE EmptyCase #-}

Welcome to these exercises on functional container abstractions!

> module FunctionalAbstractions where

Let's consider first a series of types that could contain a certain number of
things, but are generic (or parametrically polymorphic) on what type of things
they contain. Naturally, we'll start with zero, i.e. with a type that cannot
contain any of the things:

> data Zero a

Hold on though, that zero is too hardcore; not only can it not hold any things,
the type is entirely uninhabited, i.e. it holds no values at all. So what about
this, a type with a phantom parameter:

> data Phantom a = Phantom

This type, while it cannot contain any of the things, at least is inhabited. Two
kinds of zero; interesting. Wonder how that will work out.

What's next? One, right? No, wait! What about a half? Or, rather "zero or one":

> data Maybe a = Nothing | Just a

Okay, now let's do one, which from another viewpoing is the identity functor

> newtype Id a = Id a

Closely related to one, is plus one:

> data OneAnd f a = OneAnd a (f a)

Next a specialization of pair, as two:

> data Two a = Two a a

This is tedious. Let's jump from two to any number of things:

> data List a = Nil a | Cons a (List a)

Though maybe you will want to enforce that you have at least one sometimes; a
non-empty list:

> newtype NonEmptyL a = NonEmptyL (OneAnd List a)

I have also encountered times where I needed to know that there was at least two
things in the list, though I've never hit a scenario where I needed more than
that, so we can just lean on `OneAnd` for that:

> type AtLeast2 a = OneAnd NonEmptyL a

On the other hand, there are other ways to do arbitrary-length types than just
singly-linked lists, e.g.:

> data BTree a = Empty | Leaf a | Fork (BTree a) a (BTree a)

Having run up the number hierarchy a bit, let's do some logic types. First "and":

> data Pair a b = Pair a b

Next "or":

> data Either a b = Left a | Right b

Next "and/or":

> data AndOr a b = LeftOnly a | Both a b | RightOnly b

Next "if/then", i.e. the a parameter of type a can be produced if the hypothesis
r holds:

> newtype Cont r a = Cont { runCont :: r -> a }

The following function will be needed to express some laws:

> id :: a -> a
> id x = x

Now the game is to see which datatypes fit which abstractions. The rules of the
game are called laws. `Functor` has two (<$> is also known as map or fmap):
* Identity: fmap id == id
Which yields the following free theorem:
* Composition: fmap (f . g) == fmap f . fmap g

> class Functor f where
>  (<$>) :: (a -> b) -> f a -> f b

`Applicative` has the following laws (<*> is also known as apply):
* Identity: pure id <*> v = v
* Composition: pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
* Homomorphism: pure f <*> pure x = pure (f x)
* Interchange: u <*> pure y = pure ($ y) <*> u

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

`Alternative` is a monoid on applicative functors, which implies the following
laws:
* Left identity: empty <|> x = x
* Right identity: x <|> empty = x
* Associativity: x <|> y <|> z = (x <|> y) <|> z = x <|> (y <|> z)

> class Applicative f => Alternative f where
>   empty :: f a
>   (<|>) :: f a -> f a -> f a

`Monad` has the following laws (>>= is also called bind; we could add
`return` but it is just the same as `pure` for `Applicative`):
* Left identity: pure a >>= k = k a
* Right identity: m >>= pure = m
* Associativity: m >>= (\x -> k x >>= h) = (m >>= k) >>= h
There is also an ugly law that relates it to `Applicative` which I omit here.

> class Applicative f => Monad f where
>  (>>=) :: a -> f b -> f a -> f b

`MonadPlus` is a monoid on monads:

> class (Alternative m, Monad m) => MonadPlus m where
>   mzero :: m a
>   mzero = empty
>   mplus :: m a -> m a -> m a
>   mplus = (<|>)

`Contravariant`, that is, a contravariant version of `Functor`, has the
following laws:
* Identity: contramap id = id
Which yields the following free theorem:
* Composition: contramap (g . f) = contramap f . contramap g

> class Contravariant f where
>  contramap :: (b -> a) -> f a -> f b

`Bifunctor` has the following laws:
* bimap id id ≡ id
Which yields the following free theorem:
* bimap  (f . g) (h . i) ≡ bimap f h . bimap g i

> class Bifunctor f where
>   bimap :: (a -> c) -> (b -> d) -> f a b -> f c d

`Profunctor` has the following laws:
* dimap id id ≡ id
Which yields the following free theorem:
* dimap (f . g) (h . i) ≡ dimap g h . dimap f i

> class Profunctor f where
>   dimap :: (c -> a) -> (b -> d) -> f a b -> f c d

`Comonad`, the dual of `Moand`, has the following laws:
* extend extract      = id
* extract . extend f  = f
* extend f . extend g = extend (f . extend g)

> class Functor f => Comomand f where
>   extract :: f a -> a
>   extend :: (f a -> b) -> f a -> f b

Now the exercises. (Bonus points for all exercises: show that your instance is
law-abiding.)

Exericse 1: Does `Zero` have a `Functor` instance?

instance Functor Zero where
  (<$>) :: (a -> b) -> Zero a -> Zero b
  f <$> x = _

Exercise 2: Does `Phantom` have a `Functor` instance?

instance Functor Phantom where
  (<$>) :: (a -> b) -> Phantom a -> Phantom b
  f <$> x = _

Exercise 3: Does `Maybe` have a `Functor` instance?

instance Functor Maybe where
  (<$>) :: (a -> b) -> Maybe a -> Maybe b
  f <$> x = _

Exercise 4: Does `Id` have a `Functor` instance?

instance Functor Id where
  (<$>) :: (a -> b) -> Id a -> Id b
  f <$> x = _

Exercise 5: Does `OneAnd` have a `Functor`? If so, under what conditions instance?

instance Functor OneAnd f where
  (<$>) :: (a -> b) -> OneAnd f a -> OneAnd f b
  f <$> x = _

Exercise 6: Does `Two` have a `Functor` instance?

instance Functor Two where
  (<$>) :: (a -> b) -> Two a -> Two b
  f <$> x = _

Exercise 7: Does `List` have a `Functor` instance?

instance Functor List where
  (<$>) :: (a -> b) -> List a -> List b
  f <$> x = _

Exercise 8: Does `NonEmptyL` have a `Functor` instance?

instance Functor NonEmptyL where
  (<$>) :: (a -> b) -> NonEmptyL a -> NonEmptyL b
  f <$> x = _

Exercise 9: Does `AtLeast2` have a `Functor` instance?

instance Functor AtLeast2 where
  (<$>) :: (a -> b) -> AtLeast2 a -> AtLeast2 b
  f <$> x = _

Exercise 10: Does `BTree` have a `Functor` instance?

instance Functor BTree where
  (<$>) :: (a -> b) -> BTree a -> BTree b
  f <$> x = _

Exercise 11: Does `Pair` have a `Functor`? or `Pair z`, rather instance?

instance Functor (Pair z) where
  (<$>) :: (a -> b) -> Pair z a -> Pair z b
  f <$> x = _

Exercise 12: Hm, what about `Pair`'s other type argument? Doesn't it work
fundamentally the same way? How would this best be expressed?

...

Exercise 13: Does `Either z` have a `Functor` instance?

instance Functor (Either z) where
  (<$>) :: (a -> b) -> Either z a -> Either z b
  f <$> x = _

Exercise 14: Again, what about `Either`'s other type argument?

...

Exercise 15: Does `AndOr z` have a `Functor` instance?

instance Functor (AndOr z) where
  (<$>) :: (a -> b) -> AndOr z a -> AndOr z b
  f <$> x = _

Exercise 16: What about `AndOr`'s other type argument?

...

Exercise 17: Does `Cont r` have a `Functor` instance?

instance Functor (Cont r) where
  (<$>) :: (a -> b) -> Cont r a -> Cont r b
  f <$> x = _

Exercise 18: What about `Cont`'s other type argument? Is the answer similar to
the answer to this question for Exercises 12, 14, and 16, or different?

Exericse 19: Does `Zero` have an `Applicative` instance?

instance Applicative Zero where
  pure :: a -> Zero a
  pure x = _
  (<*>) :: Zero (a -> b) -> Zero a -> Zero b
  f <*> x = _

Exercise 20: Does `Phantom` have an `Applicative` instance?

instance Applicative Phantom where
  pure :: a -> Phantom a
  pure x = _
  (<*>) :: Phantom (a -> b) -> Phantom a -> Phantom b
  f <*> x = _

Exercise 21: Does `Maybe` have an `Applicative` instance?

instance Applicative Maybe where
  pure :: a -> Maybe a
  pure x = _
  (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
  f <*> x = _

Exercise 22: Does `Id` have an `Applicative` instance?

instance Applicative Id where
  pure :: a -> Id a
  pure x = _
  (<*>) :: Id (a -> b) -> Id a -> Id b
  f <*> x = _

Exercise 23: Does `OneAnd` have an `Applicative`? If so, under what conditions instance?

instance Applicative OneAnd where
  pure :: a -> OneAnd a
  pure x = _
  (<*>) :: OneAnd (a -> b) -> OneAnd a -> OneAnd b
  f <*> x = _

Exercise 24: Does `Two` have an `Applicative` instance?

instance Applicative Two where
  pure :: a -> Two a
  pure x = _
  (<*>) :: Two (a -> b) -> Two a -> Two b
  f <*> x = _

Exercise 25: Does `List` have an `Applicative` instance?

instance Applicative List where
  pure :: a -> List a
  pure x = _
  (<*>) :: List (a -> b) -> List a -> List b
  f <*> x = _

Exercise 26: Does `NonEmptyL` have an `Applicative` instance?

instance Applicative NonEmptyL where
  pure :: a -> NonEmptyL a
  pure x = _
  (<*>) :: NonEmptyL (a -> b) -> NonEmptyL a -> NonEmptyL b
  f <*> x = _

Exercise 27: Does `AtLeast2` have an `Applicative` instance?

instance Applicative AtLeast2 where
  pure :: a -> AtLeast2 a
  pure x = _
  (<*>) :: AtLeast2 (a -> b) -> AtLeast2 a -> AtLeast2 b
  f <*> x = _

Exercise 28: Does `BTree` have an `Applicative` instance?

instance Applicative BTree where
  pure :: a -> BTree a
  pure x = _
  (<*>) :: BTree (a -> b) -> BTree a -> BTree b
  f <*> x = _

Exercise 29: Does `Pair z` have an `Applicative` instance? How does the answer to this compare
with the answer for `Two`, which is essentially a specialized pair?

instance Applicative (Pair z) where
  pure :: a -> Pair z a
  pure x = _
  (<*>) :: Pair z (a -> b) -> Pair z a -> Pair z b
  f <*> x = _

Exercise 30: Does `Either z` have an `Applicative` instance?

instance Applicative (Either z) where
  pure :: a -> Either z a
  pure x = _
  (<*>) :: Either z (a -> b) -> Either z a -> Either z b
  f <*> x = _

Exercise 31: Does `AndOr z` have an `Applicative` instance?

instance Applicative (AndOr z) where
  pure :: a -> AndOr z a
  pure x = _
  (<*>) :: AndOr z (a -> b) -> AndOr z a -> AndOr z b
  f <*> x = _

Exercise 32: Does `Cont r` have an `Applicative` instance?

instance Applicative (Cont r) where
  pure :: a -> Cont r a
  pure x = _
  (<*>) :: Cont r (a -> b) -> Cont r a -> Cont r b
  f <*> x = _