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