README
partial-semigroup
Packages on Hackage:
Semigroups (background)
A semigroup is a set with a binary associative operator. In Haskell we
represent semigroups as instances of the Semigroup
typeclass, which looks
something like this:
class Semigroup a where (<>) :: a -> a -> a
This was once provided by the
semigroups package, but is
now in the Haskell standard library as of base 4.9.0.0
in 2016.
The semigroup associativity axiom
The semigroup associativity axiom is stated as:
(a <> b) <> c = a <> (b <> c)
Partial semigroups
A partial semigroup can be defined in two equivalent ways:
- As a semigroup where
<>
is a partial function (that is, we admit the possibility thatx <> y = ⊥
for somex
andy
) - As a new kind of algebraic structure where the operation is total (not
partial) but returns
Maybe a
instead ofa
.
The second definition is the approach we take here (though we will refer back to
this first definition when we discuss the associativity axiom). The
partial-semigroup
package defines the PartialSemigroup
class, which looks
like this:
class PartialSemigroup a where (<>?) :: a -> a -> Maybe a
The partial semigroup associativity axiom
The partial semigroup associativity axiom is a natural adaptation of the
semigroup associativity axiom, with a slight modification to accommodate
the situations wherein x <> y = ⊥
. First we'll express the axiom in terms
of Semigroup
and ⊥
, and then we'll rephrase it in terms of
PartialSemigroup
.
Definition 1: In terms of Semigroup
and ⊥
For all x
, y
, z
:
If
x <> y ≠ ⊥
andy <> z ≠ ⊥
, thenx <> (y <> z) = ⊥
if and only if(x <> y) <> z = ⊥
, and- where none of the terms are ⊥, the axiom for total semigroups
x <> (y <> z) = (x <> y) <> z
must hold.
Definition 2: In terms of PartialSemigroup
For all x
, y
, z
:
If
x <>? y = Just xy
andy <>? z = Just yz
, thenx <>? yz = xy <>? z
.
Deriving using GHC generics
If a type derives Generic
and all of its fields have PartialSemigroup
instances, you can get a PartialSemigroup
for free.
{-# LANGUAGE DeriveGeneric #-}
import Data.PartialSemigroup.Generics
data T
= A String (Either String String)
| B String
deriving (Eq, Generic, Show)
instance PartialSemigroup T where
(<>?) = genericPartialSemigroupOp
This gives us an implementation of <>?
which combines values only if they have
the same structure.
λ> A "s" (Left "x") <>? A "t" (Left "y")
Just (A "st" (Left "xy"))
>>> B "x" <>? B "y"
Just (B "xy")
For values that do not have the same structure, <>?
produces Nothing
.
>>> A "s" (Left "x") <>? A "t" (Right "y")
Nothing
>>> A "x" (Left "y") <>? B "z"
Nothing
Property testing
The partial-semigroup-hedgehog
package provides a
hedgehog property that you can
use to verify the associativity axiom for PartialSemigroup
instances.
The partial-semigroup-test
package aggregates all of the test packages
(although at the moment there is only one, so this package is rather
superfluous).