What is the identity of the type?
I have the following data type:
data Bull = Fools
| Twoo
deriving (Eq, Show)
and use Monoid to implement it:
instance Monoid Bull where
mempty = Fools
mappend _ _ = Fools
As you can see, mempty
this is an identical function that does not respect the laws of identity:
*Main> x = Twoo *Main> mappend mempty x == x
What will the type be Bull
? What is the identity of the type Bool
?
source to share
Short answer : it depends on the functionmappend
.
What will the type be
Bull
? What is a typeBool
?
The type has no "inherent" identifier , the identity only exists in relation to the binary function (here mappend
), for example the Wikipedia article says:
In mathematics, an identity or neutral element is a special type of set element with respect to a binary operation on that set, which leaves the other elements unchanged when combined with them.
So it depends on what kind of operation you mappend
have.
In case Bool
we define mappend = (&&)
, then the unit element is mempty = True
. But if you choose mappend = (||)
, then mempty = False
.
Yours instance Moniod Bull
doesn't match... Since it cannot satisfy the property:
mappend mempty x = x
If you choose Fools
how mempty = Fools
, then it mappend Fools Twoo
should be Twoo
. And if we choose mempty = Twoo
, then mappend Twoo Twoo
still not Twoo
.
Point a Monoid
is that you have to design the binary operator carefully. As in the Haskell documentationMonoid
, it doesn't say that it must meet the following requirements:
mappend mempty x = x
mappend x mempty = x
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty
These rules are not "made up" for Haskell: a monoid is a well-known algebraic structure . Usually in mathematics, a monoid is referred to as a 3-tuple. For example, (N, +, 0), where N is a set (for example, natural numbers), + is a binary function and 0 is a single element.
source to share
This is a great question and one that I have played several times. In fact, it was one of the first uses of universe I ever came up with, and I still find it neat. So let me show you!
Here's the idea: we're going to use the universe package to list all the possible implementations mempty
and mappend
then check which ones satisfy the laws. First, some templates:
import Data.Universe
import Data.Universe.Instances.Reverse
data Bull = Fools | Twoo deriving (Bounded, Enum, Eq, Ord, Read, Show)
instance Universe Bull
instance Finite Bull
This will simply import the appropriate bits of the package and determine your type. Now let the code work out monoid laws. We want ours to mappend
be associative; I write (+)
for mappend
, we can require:
associative (+) = all (\(x,y,z) -> (x+y)+z == x+(y+z)) universe
The laws of identity are very similar to each other and connect ours mappend
with ours mempty
(which we will call here as (+)
well zero
):
leftIdentity zero (+) = all (\x -> zero+x == x) universe
rightIdentity zero (+) = all (\x -> x+zero == x) universe
A monoid must satisfy all three laws:
monoid (zero, (+)) = associative (+) && leftIdentity zero (+) && rightIdentity zero (+)
And now we can build a list of all monoids by simply filtering out those that match the laws:
monoidsOnBull :: [(Bull, Bull -> Bull -> Bull)] monoidsOnBull = filter monoid universe
Check it out in ghci:
> mapM_ print monoidsOnBull
(Twoo,[(Fools,[(Fools,Fools),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Fools)])])
(Twoo,[(Fools,[(Fools,Twoo),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Twoo)])])
(Also, how are we supposed to read this output? Well, the universe package shows the type functions by a -> b
showing its type graph [(a, b)]
, that is, a list of input and output pairs. The output above is a tuple with a matching mempty
in the first part and a matching mappend
in the second part.)
So what are these monoids doing? Let them in turn:
(Twoo,[(Fools,[(Fools,Fools),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
Here mappend
outputs Fools
if both inputs are not Twoo
. That is, it is the Bull
equivalent (&&)
. The identity for (&&)
is True
- or Twoo
, in the case Bull
.
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Fools)])])
This one mappend
outputs Fools
if its two inputs are equal, Twoo
otherwise. You can think of it as xor on Bool
, or two's complement of 1-bit numbers. Its identity Fools
(or zero).
(Twoo,[(Fools,[(Fools,Twoo),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
This is exactly the same as the latter, but gets reset everywhere.
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Twoo)])])
This is exactly the same as the first, but everywhere it is reduced to zero. It also looks like (||)
on Bool
that has identity False
.
This ends with a lecture, but there are two more fun notes worth adding.
First, it base
offers All
and Any
, if you want yours to mappend
be (&&)
and (||)
, accordingly. As far as I know, there is no suitable new type to get xor or its negation as Monoid
; but you can fake it by declaring an instance Num
for Bool
(using intuition Word1
, which False
is 0 and True
equal to 1) to get it through Sum Bool
.
And second, here's another answer: which monoid exists for data Color = Red | Green | Blue
? We have all the mechanisms to answer this question now and to confirm that there are actually quite a few monoids:
> length monoidsOnColor
33
I encourage you to try and build code that will list them all and push them through to see what ideas you can get!
source to share
There is no monoid for a given collection (or type, in Haskell). In fact, an identity in a monoid is not defined by the set on which it is defined, but rather by an operation (which is called mappend
in Haskell). For example, a monoid on integers could be defined on add (with ID 0
) or on product (with ID 1
).
Here's why Sum
and Product
: since there are several possible implementations of a class Monoid
in a set Num a => a
, we prefer to wrap it in newtype
and define an implementation Monoid
for the wrapped type.
There are similar constructs for type Bool
c All
, monoid over booleans under concatenation ( (&&)
) with identity True
and Any
, monoid over booleans under disjunction ( (||)
) with identifier False
. In fact, Booleans can form monoids on a variety of other operations (such as XOR and XNOR).
Since the type of Bull
isomorphic type Bool
(both have exactly two null constructor), you can inspire yourself for implementation Monoid
on Bool
, but we can not decide which implementation works best in your case with a further context.
Also, as Anton Xue mentioned, even if you could define a monoid for Bull
, does it really make sense? What should be your type?
source to share