Haskell type classes: a compilation of laws

This post is a reference for type classes’ laws. It will be expanded with time.


1 Functor

class Functor f where
  fmap :: (a -> b) -> f a -> f b

1.1 Laws

  • fmap id = id
  • fmap f . fmap g = fmap (f . g)

2 Applicative

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

An alternative definition could be:

class Functor f => Applicative f where
  pure :: a -> f a
  zip :: (f a, f b) -> f (a, b)

2.1 Laws

  • pure id <*> v = v
  • pure f <*> pure x = pure (f x)
  • f <*> pure x = pure ($ x) <*> f
  • pure (.) <*> x <*> y <*> z = x <*> (y <*> z)

or:

  • zip (pure x) (pure y) = pure (x,y)
  • zip (pure x) y = fmap (x,) y
  • zip x (pure y) = fmap (,y) x
  • (\(a,(b,c)) -> ((a,b),c)) $ zip x (zip y z) = zip (zip x y) z

3 Monad

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

An alternative definition could be:

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

3.1 Laws

  • pure a >>= f = f a
  • x >>= pure = x
  • (m >>= f) >>= g = m >>= (\x -> f x >>= g)

or:

  • pure >=> f = f
  • f >=> pure = f
  • f >=> (g >=> h) = (f >=> g) >=> h

4 Alternative

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

4.1 Laws

  • empty <|> x = x
  • x <|> empty = x
  • x <|> (y <|> z) = (x <|> y) <|> z

and:

  • (f <|> g) <*> a = (f <*> a) <|> (g <|> a)
  • empty <*> a = empty
  • f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
  • f <$> empty = empty

5 Foldable

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

5.1 Laws

There are no laws. However, when it is also a functor, it is expected that:

  • foldMap f . fmap g = foldMap (f . g)

also, if t is monoid morphism, that is:

t mempty = mempty
t (a <> b) = t a <> t b

it is expected that:

  • t . foldMap f = foldMap (t . f)

6 Traversable

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

6.1 Laws

Let t be an applicative transformation, that is:

t (pure a) = pure a
t (a <*> b) = t a <*> t b

then:

  • t . traverse f = traverse (t . f)
  • traverse Identity = Identity
  • traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

and:

  • traverse (Identity . f) = Identity . fmap f
  • traverse (Const . f) = Const . foldMap f