partial-semigroup
A partial binary associative operator
https://github.com/typeclasses/partial-semigroup
LTS Haskell 22.33: | 0.6.0.2@rev:1 |
Stackage Nightly 2023-12-26: | 0.6.0.2@rev:1 |
Latest on Hackage: | 0.6.0.2@rev:1 |
partial-semigroup-0.6.0.2@sha256:ce41c0e44ce089b54de0bf97b0e6c07123a8c3655e106b6fc1f672fc70433fd4,1769
Module documentation for 0.6.0.2
A partial semigroup is like a semigroup, but the operator is partial. We represent this in Haskell as a total function:
(<>?) :: a -> a -> Maybe a
The partial-semigroup-hedgehog companion package provides support for checking the partial semigroup associativity axiom using the hedgehog package.
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 ≠ ⊥
, then-
x <> (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
Changes
0.6.0.2 - 2023 June 26
- Raise language version to GHC2021
0.6.0.1 - 2023 Jan 10
- Support GHC 9.4
0.6.0.0 - 2022 Mar 21
- Raise minimum bound for
base
to 4.13 (GHC 8.8) - Raise supported
hedgehog
range to 1.0, 1.1 - Remove all cabal flags
- Remove doctest test-suite
0.5.1.14 - 2022 Jan 10
- Support GHC 9.2
0.5.1.12 - 2021 May 27
- Add support for GHC 9.0
0.5.1.10 - 2021 May 27
- Drop support for GHC 7.10
0.5.1.8 - 2020 Jun 2
- Support
doctest-0.17
0.5.1.6 - 2020 May 20
- Support GHC 8.10
0.5.1.4 - 2020 Apr 1
- Support GHC 8.8
0.5.1.1 - 2019 May 14
- Bump upper version bound to allow building with Hedgehog 1.0
0.5.1.0 - 2019 Feb 13
- Add
One
andAtMostOne
0.5.0.0 - 2018 Nov 21
- Drop support for GHC 7.8 and below
0.4.0.1 - 2018 Sep 27
- Support GHC up to 8.6
0.4.0.0 - 2018 Sep 27
- Remove the
Monoid
instance onPartial
- Support GHC up to 8.4
0.3.0.3 - 2018 Feb 13
- Bump upper version on doctest dependency
0.3.0.2 - 2017 Oct 23
- Remove the
Generics
module when building with GHC 7.4
0.3.0.1 - 2017 Oct 23
- Add the
Data.PartialSemigroup.Generics
module
0.2.0.1 - 2017 Oct 23
- Add support for GHC versions 7.4 through 8.2
0.1.0.3 - 2017 Oct 17
- Very minor code style and cabal metadata changes
0.1.0.1 - 2017 Oct 17
- Rename
appendMaybe
to(<>?)
0.0.0.1 - 2017 Oct 17
- Initial release