Functional Programming Refresher

Source: Dev.to

Magma

A Magma is a set with a (closed) binary operation.

Semigroup

A Semigroup is a magma where the operation is associative.

class Semigroup a where
  (<>) :: a -> a -> a
  -- ^ read as "append"

Must satisfy:

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

Example

[1,2] <> [3,4] <> [5] == [1,2,3,4,5]

Monoid

A Monoid is a semigroup with an identity element.

class Semigroup a => Monoid a where
  mempty :: a
  -- ^ identity element of <>

Must satisfy:

mempty <> x == x               -- left identity
x <> mempty == x               -- right identity
(x <> y) <> z == x <> (y <> z) -- associativity (from Semigroup)

Note: mappend is a historical name for <> and is now deprecated.

Example

mempty <> [1,2] == [1,2]
singleton 1 <> mempty == singleton 1

Group

A Group is a monoid where every element has an inverse.

class Monoid a => Group a where
  invert :: a -> a
  -- ^ inverse of <>

Must satisfy:

x <> invert x == mempty == invert x <> x

Functor

A Functor represents a type that can be mapped over.

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  -- ^ map a function over a structure
  ( f b -> f a
  -- ^ replace all locations in the input with the same value

Must satisfy:

fmap id == id                         -- identity
fmap (f . g) == fmap f . fmap g       -- composition

Example

fmap (*2) [1,2,3]        == [2,4,6]
fmap negate (Just 2)    == Just (-2)

The infix version of fmap is “:

(*2)  [1,2,3]   == [2,4,6]
negate  Just 2  == Just (-2)

Applicative

An Applicative functor supports function application within its context.

class Functor f => Applicative f where
  pure  :: a -> f a
  -- ^ "box" a value into the context
  () :: f (a -> b) -> f a -> f b
  -- ^ apply a function inside a context to a value inside a context

Must satisfy:

pure id  v                     == v                     -- identity
pure (.)  u  v  w        == u  (v  w)      -- composition
pure f  pure x                == pure (f x)           -- homomorphism
u  pure y                      == pure ($ y)  u     -- interchange

Example

(Just (*2)  Just 4) == Just 8
(+)  Just 2  Just 3 == Just 5

Applicatives can be traversed with Data.Traversable.
Sequence actions, discarding the value of the first argument:

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

Monad

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  -- ^ sequentially compose two actions, passing any value produced by the first as an argument to the second
  (>>)  :: m a -> m b -> m b
  -- ^ sequencing operator that discards the result of the first action

Must satisfy:

return a >>= k   == k a          -- left identity
m >>= return     == m           -- right identity
m >>= (\x -> k x >>= h) == (m >>= k) >>= h   -- associativity

Example

(Just 4 >>= \x -> Just (x * 2)) == Just 8

MonoidalMap

A MonoidalMap is a Map variant which uses the value’s Monoid instance to accumulate conflicting entries when merging maps.

If the order of arguments doesn’t matter, the operation is Commutative.

Example

a + b == b + a
[1,2] <> [3,4] /= [3,4] <> [1,2]

Distributive

Two functions distribute over each other if they can be interchanged without affecting the result: f . g = g . f.

Example

a * (b + c) == (a * b) + (a * c)

Free Constructions

A free construction is one in which the mandatory laws hold, but no additional laws hold.

• The free monoid is a list.
• The free commutative monoid is a multiset.