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.


[Skip to Readme]

Downloads

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
Change log changelog.md
Dependencies base (>=4.14 && <4.18) [details]
License Apache-2.0
Copyright 2021 Mission Valley Software LLC
Author Chris Martin
Maintainer Chris Martin, Julie Moronuki
Category Algebra
Home page https://github.com/typeclasses/partial-semigroup
Bug tracker https://github.com/typeclasses/partial-semigroup/issues
Source repo head: git clone https://github.com/typeclasses/partial-semigroup
Uploaded by chris_martin at 2023-01-10T21:27:17Z
Distributions LTSHaskell:0.6.0.1, NixOS:0.6.0.0, Stackage:0.6.0.1
Reverse Dependencies 2 direct, 1 indirect [details]
Downloads 8377 total (74 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-01-10 [all 1 reports]

Readme for partial-semigroup-0.6.0.1

[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