Common Typeclasses

A great resource for information on common typeclasses in Haskell is the typeclassopedia. We recommend reading that document, and following up here for additional pointers.

Section exercises:

• Write the foldMapM helper function
• Implement the Validation Applicative
  • Why isn't it a Monad?

Overview

• Not going to cover these in depth
• Great resource on this: typeclassopedia

Hysterical raisins

• Applicative wasn't a superclass of Monad in the past
• Semigroup wasn't a superclass of Monoid in the past
• Some unnecessary functions still lying around
• Sometimes functions aren't as general as we wish

Functor

• "Mappable"
• Provides fmap :: (a -> b) -> (f a -> f b)
• Laws
  • fmap id == id
  • fmap (g . h) == fmap g . fmap h
• Cool fact: only one possible valid instance per type
• Can be derived automatically
• Covariant functor (contravariant also exists)
• See: Covariance and Contravariance

Applicative

Provides:

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

Compare:

fmap  ::   (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b

Also note that you can define fmap using Applicative

fmap g x = pure g <*> x

Laws:

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

Monad

Provides:

(>>=) :: m a -> (a -> m b) -> m b

Or flipped:

(=<<) :: (a -> m b) -> m a -> m b

Compare:

fmap  ::   (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b
(=<<) :: (a -> m b) -> m a -> m b

Laws:

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

And we can define:

(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)

And then restate these laws as:

f <=< pure == f
pure <=< f == f
(h <=< g) <=< f == h <=< (g <=< f)

Which are the same as the category laws:

f . id == f
id . f == f
(h . g) . f == h . (g . f)

Semigroup and Monoid

Summary explanation: Semigroup defines a binary, associative operator.

(<>) :: a -> a -> a

Law

(x <> y) <> z == x <> (y <> z)

Monoid is a subclass of Semigroup, and adds an identity to Semigroup.

mempty :: a

The laws are the same again as Monad and categories!

x <> mempty == x
mempty <> x == x
(x <> y) <> z == x <> (y <> z)

More worked explanation: Semigroup is a typeclass that provides a single binary, associative operator. For example, for integers, + and * are both valid Semigroup implementations. For lists, appending two lists forms a Semigroup.

Monoid builds on Semigroup, but adds in an identity, where it follows the law that applying that binary operator as either the left or right value to the identity is a no-op

In other words: 0 + x = x, x + 0 = x, and (a + b) + c = a + (b + c). Therefore: (<>) = (+) and mempty = 0 forms a valid Semigroup/Monoid pair of instances. Some things are a Semigroup, but not a Monoid. A simple example: a non-empty list. While you can append together two non-empty lists, there's no identity value you can come up with where the identity laws hold.

That's all the technical definition. Intuition: Semigroup and Monoid let you define a way to slam data together!

EXERCISE Write a data type for calculating the average of a bunch of values. The data type will need to have two fields: one to keep the running sum, one the running total. Then write Semigroup and Monoid instances that Do The Right Thing, define an average function that calculates the average from these two fields, and you're done. Try using fold (part of the Foldable typeclass we'll cover next) to summarize a list of values.

Foldable

• "I can be turned into a list" but more efficient in some cases.
• foldMap :: Monoid m => (a -> m) -> f a -> m
• Can be derived automatically
• No actual laws yet
• Could define a Vector that folds left-to-right or right-to-left
• length of tuples and other things considered surprising/wrong by many

Traversable

• "Map with effects"
• Generalizes mapM
• traverse == mapM, but works for Applicative
• for == forM, but for Applicative

Exercises

See start of section