[Haskell-cafe] instance Monoid a => Monad ((,) a)

[Tom Ellis]

When this question came up the other day I started to wonder how many
boolean operators are monoidal.  I wrote a program to check.

There are eight associative operators (i.e. that give rise to semigroups). 
They are

const True
or
const
flip const
xnor
and
xor
const False

Only four of these have an identity (i.e. give rise to monoids).  They are

or
xnor
and
xor

Tom



> putStrLn showMonoids
Semigroups
TT=T TF=T FT=T FF=T
TT=T TF=T FT=T FF=F
TT=T TF=T FT=F FF=F
TT=T TF=F FT=T FF=F
TT=T TF=F FT=F FF=T
TT=T TF=F FT=F FF=F
TT=F TF=T FT=T FF=F
TT=F TF=F FT=F FF=F
Monoids
TT=T TF=T FT=T FF=F
TT=T TF=F FT=F FF=T
TT=T TF=F FT=F FF=F
TT=F TF=T FT=T FF=F


allOfThem :: [Bool]
allOfThem = [True, False]

binops :: [Bool -> Bool -> Bool]
binops = do
  tt <- allOfThem
  tf <- allOfThem
  ft <- allOfThem
  ff <- allOfThem

  let f True  True  = tt
      f True  False = tf
      f False True  = ft
      f False False = ff

  pure f

associative :: (Bool -> Bool -> Bool) -> Bool
associative (.*) = and $ do
  x <- allOfThem
  y <- allOfThem
  z <- allOfThem

  pure (x .* (y .* z) == (x .* y) .* z)

identity :: (Bool -> Bool -> Bool) -> Bool
identity (.*) = or $ do
  i <- allOfThem

  return (and $ do
             x <- allOfThem
             [x .* i == x, i .* x == x])

semigroups :: [Bool -> Bool -> Bool]
semigroups = filter associative binops

monoids :: [Bool -> Bool -> Bool]
monoids = filter identity semigroups

showBool :: Bool -> String
showBool True  = "T"
showBool False = "F"

showBinop :: (Bool -> Bool -> Bool) -> String
showBinop (.*) = unwords $ do
  x <- allOfThem
  y <- allOfThem

  pure (showBool x ++ showBool y ++ "=" ++ showBool (x .* y))

showMonoids :: String
showMonoids = (unlines . concat) [
    ["Semigroups"]
  , map showBinop semigroups
  , ["Monoids"]
  , map showBinop monoids
  ]


On Mon, Aug 05, 2019 at 04:49:41PM -0400, David Feuer wrote:
> Bool is also a monoid under xor.
> 
> On Mon, Aug 5, 2019, 4:34 PM Jinxuan Zhu <zhujinxuan at gmail.com> wrote:
> 
> > Hi, I think the error message says there is no Monoid for Bool.  It is
> > because Bool can be monoid by either || or && operations, which would lead
> > to ambiguity if Bool is monoid by default.
> >
> > You can:
> > 1. use Maybe Unit instead
> > 2. (overkill) Define AndMonoid Bool newtype and use DeriveVia and coerce
> >
> > On Fri, Aug 2, 2019 at 7:39 PM Benjamin Franksen <ben.franksen at online.de>
> > wrote:
> >
> >> I wanted to define a simple Monad instance for (Bool,) as
> >>
> >> instance Monad ((,) Bool) where
> >>   return x = (False, x)
> >>   (True, x) >>= k = (True, snd (k x))
> >>   (False, x) >>= k = k x
> >>   -- or: (b, x) >>= k = let (c, y) = k x in (b||c, y)
> >>
> >> The idea was to keep track of whether functions change their input value
> >> or not.
> >>
> >> To my astonishment I found that this definition overlaps with an
> >> existing one. GHC tells me
> >>
> >> x.hs:2:10: error:
> >>     • No instance for (Monoid Bool)
> >>         arising from the superclasses of an instance declaration
> >>     • In the instance declaration for ‘Monad ((,) Bool)’
> >>   |
> >> 2 | instance Monad ((,) Bool) where
> >>   |          ^^^^^^^^^^^^^^^^
> >>
> >> x.hs:2:10: error:
> >>     • Overlapping instances for Monad ((,) Bool)
> >>         arising from a use of ‘GHC.Base.$dm>>’
> >>       Matching instances:
> >>         instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
> >>         instance Monad ((,) Bool) -- Defined at x.hs:2:10
> >>     • In the expression: GHC.Base.$dm>> @((,) Bool)
> >>       In an equation for ‘>>’: (>>) = GHC.Base.$dm>> @((,) Bool)
> >>       In the instance declaration for ‘Monad ((,) Bool)’
> >>   |
> >> 2 | instance Monad ((,) Bool) where
> >>   |          ^^^^^^^^^^^^^^^^
> >>
> >> [one more similar overlap error elided]
> >>
> >> But I could not find the
> >>
> >>   instance Monoid a => Monad ((,) a)
> >>
> >> documented anywhere in the base package. Should I look harder? Or is
> >> this instance accidentally leaking from GHC.Base?
> >>
> >> Eventually, through some experimenting I found that if I replace Bool
> >> with Any, then the existing instance seems to do what I want.