[Haskell-cafe] instance Monoid a => Monad ((,) a)
Tom Ellis
tom-lists-haskell-cafe-2017 at jaguarpaw.co.uk
Tue Aug 6 12:15:01 UTC 2019
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.
More information about the Haskell-Cafe
mailing list