A Magma is a set with a (closed) binary operation.
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]
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
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
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
(<$) :: a -> 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)
An Applicative functor supports function application within their 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
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
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, it's indicative that the operation is Commutative.
Example:
a + b == b + a
[1,2] <> [3,4] /= [3,4] <> [1,2]
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)
A free construction is one in which the mandatory laws hold, but in which absolutely no other laws hold. The free monoid is a list, and the free commutative monoid is a multiset.
Top comments (0)