# partial-semigroup: A partial binary associative operator

[ algebra, apache, library ] [ Propose Tags ]

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.

#### Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

• No Candidates
Versions [RSS] 0.0.0.1, 0.1.0.1, 0.1.0.2, 0.1.0.3, 0.2.0.1, 0.3.0.1, 0.3.0.2, 0.3.0.3, 0.4.0.0, 0.4.0.1, 0.5.0.0, 0.5.1.0, 0.5.1.1, 0.5.1.4, 0.5.1.6, 0.5.1.8, 0.5.1.10, 0.5.1.12, 0.5.1.14, 0.6.0.0, 0.6.0.1 changelog.md base (>=4.14 && <4.18) [details] Apache-2.0 2021 Mission Valley Software LLC Chris Martin Chris Martin, Julie Moronuki Algebra https://github.com/typeclasses/partial-semigroup https://github.com/typeclasses/partial-semigroup/issues head: git clone https://github.com/typeclasses/partial-semigroup by chris_martin at 2023-01-10T21:27:17Z LTSHaskell:0.6.0.1, NixOS:0.6.0.0, Stackage:0.6.0.1 2 direct, 1 indirect [details] 8377 total (74 in the last 30 days) 2.0 (votes: 1) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2023-01-10

[back to package description]

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:

1. As a semigroup where <> is a partial function (that is, we admit the possibility that x <> y = ⊥ for some x and y)
2. As a new kind of algebraic structure where the operation is total (not partial) but returns Maybe a instead of a.

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 ≠ ⊥ and y <> 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 and y <>? z = Just yz, then

• x <>? 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