

In [ ]:

    
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}


import Prelude hiding ((.), id, Functor, Monad)

Category



In [ ]:

    
-- Morphisms
type (a ~> b) c = c a b

class Category (c :: k -> k -> *) where
  id :: (a ~> a) c
  (.) :: (y ~> z) c -> (x ~> y) c -> (x ~> z) c

id x . f ≡ f
f . id x ≡ f

Example



In [ ]:

    
type Hask = (->)

instance Category Hask where
  id x = x
  (f . g) x = f (g x)

Functor



In [ ]:

    
class (Category c, Category d) => Functor c d t where
  fmap :: c a b -> d (t a) (t b)

fmap id ≡ id
fmap (a . b) ≡ (fmap a) . (fmap b)

Example



In [ ]:

    
instance Functor Hask Hask [] where
  fmap f [] = []
  fmap f (x:xs) = f x : (fmap f xs)

Natural Transformations



In [ ]:

    
type Nat f g = forall a. f a -> g a

fmap f . g ≡ g . fmap f

Example



In [ ]:

    
headMay :: forall a. [a] -> Maybe a
headMay []     = Nothing
headMay (x:xs) = Just x

Monad



In [ ]:

    
class Functor c c f => Monad c f where
  return :: c a b -> f (c a b)
  join :: f (f (c a b)) -> f (c a b)

fmap g . return = return . g
fmap g . join = join . fmap (fmap g)
join . fmap join = join . join
join . return = id = join . fmap return

Example



In [ ]:

    
instance Monad Hask [] where
    return x = [x]
    join (sublist:xs) = sublist ++ join xs