Popularity
6.1
Growing
Activity
4.1
-
14
3
4

Monthly Downloads: 66
Programming language: Haskell
License: Apache License 2.0
Tags: Algebra     Partial    
Latest version: v0.5.0.0
Add another 'partial' Package

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:

  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

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).