Apache-2.0 licensed by Chris Martin
Maintained by Chris Martin, Julie Moronuki
This version can be pinned in stack with:partial-semigroup-0.6.0.1@sha256:db73114cc43c7a8875bab96a782649b47775a1b27bac3e45049c156446ad3c30,1757

Module documentation for 0.6.0.1

Depends on 1 package(full list with versions):

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

Changes

0.6.0.1 - 2022 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 and AtMostOne

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 on Partial
  • 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