Monoid over XOR or XNOR, and Monoid lifted by Applicative.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Monoid over XOR or XNOR, and Monoid lifted by Applicative.

박신환

Logical XOR is associative, also is XNOR. And they both have an identity element.

 

Hence:

 

newtype Even = Even {getEven :: Bool} 

newtype Odd = Odd {getOdd :: Bool}

 

instance Semigroup Even where

    (<>) = (==) -- (==) over Bool == Logical XNOR 

 

instance Semigroup Odd where

    (<>) = (/=) -- (/=) over Bool == Logical XOR 

 

instance Monoid Even where

    mempty = True

 

instance Monoid Odd where

    mempty = False

 

So foldMap would determine the parity of the number of Trues. 

 

 

Also, Monoid lifted by Applicative is also Monoid. This might be useful:

 

newtype AMonoid f a = AMonoid {getAMonoid :: f a}

 

instance (Applicative f, Semigroup a) => Semigroup (AMonoid f a) where

    (<>) = liftA2 (<>)

 

instance (Applicative f, Monoid a) => Monoid (AMonoid f a) where

    mempty = pure mempty

 


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Monoid over XOR or XNOR, and Monoid lifted by Applicative.

Andrew Martin
I agree that the AMonoid type you describe is useful. In fact, it's going to be in base when GHC 8.6 is released: https://github.com/ghc/ghc/pull/123

On Wed, May 2, 2018 at 10:31 AM, 박신환 <[hidden email]> wrote:

Logical XOR is associative, also is XNOR. And they both have an identity element.

 

Hence:

 

newtype Even = Even {getEven :: Bool} 

newtype Odd = Odd {getOdd :: Bool}

 

instance Semigroup Even where

    (<>) = (==) -- (==) over Bool == Logical XNOR 

 

instance Semigroup Odd where

    (<>) = (/=) -- (/=) over Bool == Logical XOR 

 

instance Monoid Even where

    mempty = True

 

instance Monoid Odd where

    mempty = False

 

So foldMap would determine the parity of the number of Trues. 

 

 

Also, Monoid lifted by Applicative is also Monoid. This might be useful:

 

newtype AMonoid f a = AMonoid {getAMonoid :: f a}

 

instance (Applicative f, Semigroup a) => Semigroup (AMonoid f a) where

    (<>) = liftA2 (<>)

 

instance (Applicative f, Monoid a) => Monoid (AMonoid f a) where

    mempty = pure mempty

 


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries




--
-Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Monoid over XOR or XNOR, and Monoid lifted by Applicative.

Edward Kmett-2
In reply to this post by 박신환
In that same light, we're also missing packaged monoids for the bitwise (.|.), (.&.), xor (and the non-existent xnor) from Data.Bits. Bool is an instance of Bits. Extending this to these more general types you'd get:

newtype And a = And { getAnd :: a }
newtype Or a = Or { getOr :: a }
newtype Even a = Even { getEven :: a }
newtype Odd a = Odd { getOdd :: a }

Once things move to arbitrary bitwise operations, Even/Odd may not be the best names, though they do perform "vertical" bitwise parity checks.

While I don't have a particularly strong preference about whether those extra instances should live in Data.Monoid or Data.Bits, due to Monoid now being in Prelude, users do import Data.Monoid unqualified in rather more code than Bits. This would give me a slight preference to placing these in Data.Bits, but if one or the other would create an import cycle in base, I think it'd be fine to let that trump such a concern and force the placement.

-Edward

On Wed, May 2, 2018 at 10:31 AM, 박신환 <[hidden email]> wrote:

Logical XOR is associative, also is XNOR. And they both have an identity element.


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Monoid over XOR or XNOR, and Monoid lifted by Applicative.

M Farkas-Dyck-2
On 5/5/18, Edward Kmett <[hidden email]> wrote:
> In that same light, we're also missing packaged monoids for the bitwise
> (.|.), (.&.), xor (and the non-existent xnor) from Data.Bits.

I defined a `BitSet` type in my alg package:
http://hackage.haskell.org/package/alg
(Building docs failed, so here is the definition: `newtype BitSet a =
BitSet { bits :: a }`)

The `Monoid` instance is (`False`, `xor`) (wasn't thinking about xnor,
stupid me).

I was also trying to define `Monoid` instances for `Min (BitSet a)`
and `Max (BitSet a)` but alas, they overlap, tho `BitSet` is not `Ord`
(so usual instances are useless).

Maybe we want a `Lattice` class?
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Monoid over XOR or XNOR, and Monoid lifted by Applicative.

Edward Kmett-2
There are several packagings of lattices and semilattices strewn across hackage, and not much convergence on any single one.

Sent from my iPhone

> On May 5, 2018, at 4:54 PM, Matthew Farkas-Dyck <[hidden email]> wrote:
>
>> On 5/5/18, Edward Kmett <[hidden email]> wrote:
>> In that same light, we're also missing packaged monoids for the bitwise
>> (.|.), (.&.), xor (and the non-existent xnor) from Data.Bits.
>
> I defined a `BitSet` type in my alg package:
> http://hackage.haskell.org/package/alg
> (Building docs failed, so here is the definition: `newtype BitSet a =
> BitSet { bits :: a }`)
>
> The `Monoid` instance is (`False`, `xor`) (wasn't thinking about xnor,
> stupid me).
>
> I was also trying to define `Monoid` instances for `Min (BitSet a)`
> and `Max (BitSet a)` but alas, they overlap, tho `BitSet` is not `Ord`
> (so usual instances are useless).
>
> Maybe we want a `Lattice` class?
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries