Type Class Notes


Haskell's typeclasses


Haskell's Functor is a type class. Any type constructor that implements Functor's fmap is a functor. To be more technical, the type constructor + implementation of fmap is an endofunctor on Hask.


If `((,) e)` is a type constructor, it means a tuple type of two elements with the first being `e` while the second is a type variable.

Note that `((,) 1)` is a function. It's type is not `Num a => ((,) a)`


For Monad, think of `m a` as a computation with `a` being the return result. `return` means "null computation" which accepts `a` and returns `a` in the computation context. `>>=` composes two computation into another computation.

Based on this, it's easy to understand the reader Monad.

```haskell:ReaderMonad.hs

const a b = a

instance Monad ((->) e) where
  return = const
  m >>= f = \x -> f (m x) x

```

Here, `const` will return a computation which simply ignores the arguments passed in and return value passed to `return`. `m` is a computation. `>>=` combines one computation with another computation generator, that is `f`. `f` generates another computation based on the result of computation `m`.


What can be a reader monad? Every function that accepts an argument and returns a value can be a reader monad. For example, sometimes the argument passed in can be an environment. The function will lookup some variable in the environment and return it directly or modify it in the environment.

How to prove two laws are equivalent?
--
No Idea

We already have fmap, why do we still need liftM?
-- 

Theoretically, every Monad is also a Functor. So 'fmap == liftM'. However, in haskell's standard library, Monad type class doesn't require Functor instance. So we have 'liftM' to avoid an explicit 'Functor' constraint.


Multi-parameter type class and Functional Dependencies.
--

Take type class `Eq` as an example, Haskell's type class declaration is like:

```hs

class Eq a where
  (==) :: a -> a -> Bool
```
The declaration can be read as:


> Type a is a member of type class `Eq`

So Haskell's type class is like a set of types with the types (also called instance) follow the constraint of the class by implementing all the function declared.

```hs

instance Eq Bool where
  a == b = if a then b else not b
  
```

Here, we declare that `Bool` belongs to set `Eq`, or $ Bool \in Eq $. The curry style declaration is a little misleading. 

We can also declare one type class as the super class of another.

```hs

class Eq a => Ord a where
  (<), (<=) :: a -> a -> Bool

```

This declaration can be read as

> Type class `Ord` implies Type class `Eq`
> Or, if a type is a member of `Ord`, then it must be a member of `Eq`
> Or, `Eq` is a super class of `Ord`

Super class declaration makes sure that one type class can inherit the constraint of another type class. 

Haskell also allows multi-parameter type class. One classical example is to implement uniform interfaces for Collection.

```hs

class Collection e ce where
  empty :: ce
  insert :: e -> ce -> ce
  member :: e -> ce -> Bool

```

`List` is an instance of `Collection` type class.

```hs

instance Collection Int [Int] where
  empty = []
  insert = (:)
  member = elem

```

Run a small program to check out type class

```hs

demo = let x :: Int
            x = 3
         in insert x empty

main = print demo
```

Compile it with GHC, it will report some scary errors:

```hs


multi-param.hs:67:12:
    No instance for (Collection Int a0) arising from a use of ‘insert’
    The type variable ‘a0’ is ambiguous
    Relevant bindings include demo :: a0 (bound at multi-param.hs:65:1)
    Note: there is a potential instance available:
      instance Collection Int [Int] -- Defined at multi-param.hs:59:10
    In the expression: insert x empty
    In the expression:
      let
        x :: Int
        x = 3
      in insert x empty
    In an equation for ‘demo’:
        demo
          = let
              x :: Int
              x = 3
            in insert x empty

...

```


The reason is that when GHC evaluating `insert x empty`, it will firstly infer the types of expressions involved and then find the instance by unifying the types of expressions.

```hs

x :: Int
empty :: Collection e ce => ce
insert :: Collection e ce => e -> ce -> ce

```

Apparently, `x`'s type is known because we have explicitly annotated it. However, type of `empty` is unknown, so GHC directly represents it as a type variable $ \alpha $. Based on `x` and `empty`, we will get type of `insert` : $ Collection \space Int \space \alpha => Int \rightarrow \alpha \rightarrow \alpha $. We haven't declared the instance $ Collection \space Int \space \alpha $, which leads GHC to complain.


Faced with the problem, you might be tempted to annotate type of `empty` explicitly.

```hs

demo = let x :: Int
           x = 3
           ec :: [Int]
           ec = empty
        in insert x ec

```

This still doesn't work since the `empty` function has an ambiguous type: `empty : Collection e [Int] => [Int]` since type variable `e` appears on the left of `=>` symbol(See [qualified types]). (I don't quite get this, maybe I will read the paper first). Also the instance `Collection e [Int] => [Int]` is also not defined, which is just what GHC reports.

We can solve this by replacing `empty` with `[]`, but this makes `empty` function meaningless. Functional dependency is one reasonable solution.


```hs
class Collection e ce | ce -> e where
  empty :: ce
  insert :: e -> ce -> ce
  member :: e -> ce -> Bool


instance Collection Int [Int] where
  empty = []
  insert = (:)
  member = elem


demo = let x :: Int
           x = 3
           ec :: [Int]
           ec = empty
        in insert x empty

```

Here, `ce -> e` is functional dependency. It means that `ce determines e`. Or, if you have already determined `ce`, then `e` is determined. Or, for if `ce` is determined, there is only one corresponding instance implementation. 

The annotation is quite intuitive. `ce -> e` looks like a function, whose definition requires for each `ce` there is only one corresponding `e`. 

Unfortunately, we still can't write code like:

```
demo = let x :: Int
           x = 3
        in insert x empty

```

Since without explicit annotation, the type of `empty` is still unknown, which leads to wrong inferred instance: `Collection Int a`.)

OCaml's Modules are claimed to be [*much* more expressive][OCaml Module] than type class. 


ReaderT
--

```hs
ask :: (Monad m) => ReaderT r m r
ask = ReaderT return
```

`return` is a polymorphic function with type: `a -> m a`, which just fits in `ReaderT`'s constructor. The type of `m` depends on how you defines it. A small demo to show how `ask` works:

```hs

demo = let y :: Int
           y = 3
           x :: Either String Int
           x = runReaderT (ReaderT return) y
        in x
```
Here, I define `m` as Either Monad. You can also define it as Maybe Monad or whatever you want.



Continuation Monad
--


take function square as an example

```hs

square x = x*x

-- change it into continuation passing style

square_cont x = \k -> k (square x)

```

The return value of `square_cont` is called suspended computation. After passing a continuation:`k` to suspended computation, it will calculate the intermediate result(returned by `square` function). The return value of `k` is the return value of the suspended computation.

Suspended computation "wraps" all the computation of "square" and pass the result to "future computation"/Continuation of `square`:`k`. The main responsibility of suspended computation is getting `k`, conducting the wrapped computation and passing computation result to `k`.
Get a sense of suspended computation through following examples:

```hs

main = let suspended_computation = square_cont 3
        in do
          print $ suspended_computation (*2)
          print $ suspended_computation (*3)

```


Continuation Monad is just the suspended computation. Continuation monad can be used to compose functions in continuation passing style. 


```hs

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

```

for example:

```hs

import Control.Monad.Identity
import Control.Monad.Cont

square:: (Num a) => a -> a
square x = x*x


square_cont :: (Num a) => a -> Cont b a
square_cont x = cont $ \k -> k (square x)

main = print $ runCont (square_cont 4) show

```
 
`cont` construct a continuation monad. `runCont` execute the continuation monad after passing continuation to it. 

For `Cont b a`, `b` is final result type(return type of future continuation), `a` is intermediate result type.

A continuation monad transformer can bind a future continuation with a monadic computation to form a continuation monad. The future continuation accepts the result of monadic computation and return a monadic computation with new result. 



callCC
===

callCC or call-with-current-continuation, gives explicit control of continuation. 

```hs

foo = callCC $ \k -> (k "hello world") >> (return "never printed")

main = print $ runCont foo show

```

callCC returns a suspended computation, which is often called "callCC computation". For whatever value passed to k is captured in the callCC computation, and the computation after k is ignored. 


```hs

-- callCC accepts a function f and return a Continuation Monad.
-- f accepts a function k as arguments
-- f :: (a -> ContT r m b) -> ContT r m a
-- k :: a -> ContT r m b
-- x :: a
-- c :: a -> m r

callCC::((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT $ \ c -> runContT (f (\ x -> ContT $ \ _ -> c x)) c

```

In `callCC`, `c` is actually "current continuation", i.e, the continuation of the `callCC` expression, or, what the program will do after the `callCC` is called. So, you can see, it's called "call with current continuation" not without reason.
 
All the magic of `callCC` starts with the function `f` that Haskell programmer has to implement. callCC passes another function `k` to `f`. As you can see, the implementation of `k` is simple but very confusing.

```haskell:k.hs

-- sub function extracted from callCC
k :: a -> ContT r m b
k = \ x -> ContT $ \ _ -> c x

```

In the example above, `x` is "hello world". `k` simply returns a special suspended computation which ignores following continuation and replace it with `c`. So when the Continuation Monad returned by calling `k` with "hello world" is bound(i.e, `>>=`) with another Continuation Monad : `(return "never printed)`, the continuation encapsulated in it will not be executed. Also, running `ContT $ \ _ -> c x` with another Continuation will lead the continuation ignored. So `runContT (f (\ x -> ContT $ \ _ -> c x)) c` simply executes `c x`. 

In function `f`, `k` may not be called. In this case, body of `f` will be executed until the last expression. Then `runContT (f (\ x -> ContT $ \ _ -> c x)) c` will pass `c` as continuation to the Continuation Monad returned by `f`. 


Foldable
---

type of `foldMap . foldMap` is `(a -> m) -> t1 (t2 a) -> m`. type of `foldMap` is `(a -> m) -> t2 a -> m`. So you can think of `foldMap` as a function which transforms a function of type `(a->m)` to type `(t2 a -> m)`. So for `foldMap . foldMap`, the right `foldMap` transforms `a->m` to `t2 a -> m`, then the left `foldMap` transforms `t2 a -> m` to `t1 (t2 a) -> m`.  




[OCaml Module]: http://qr.ae/qk4eP
[qualified types]:https://www.cs.ox.ac.uk/files/3432/PRG106.pdf