Copyright	(c) 2020 Reed Mullanix Emily Pillmore
License	BSD-style
Maintainer	Reed Mullanix <reedmullanix@gmail.com>, Emily Pillmore <emilypi@cohomolo.gy>
Stability	stable
Portability	non-portable
Safe Haskell	Safe
Language	Haskell2010

Data.Group.Foldable

Contents

Group foldable
- Group foldable combinators

Description

This module provides definitions GroupFoldable, along with useful combinators.

Synopsis

class GroupFoldable t where
- goldMap :: Group g => (a -> g) -> t a -> g
- toFG :: t a -> FG a
gold :: (GroupFoldable t, Group g) => t g -> g
goldr :: GroupFoldable t => Group g => (a -> Permutation g) -> t a -> Permutation g
toFreeGroup :: (GroupFoldable t, Group g) => t g -> FreeGroup g

Group foldable

class GroupFoldable t where Source #

The class of data structures that can be groupoidally folded.

GroupFoldable has difficult-to-define laws in terms of Haskell, but is well-understood categorically: GroupFoldables are functors (not necessarily Functors) in the slice category \( [\mathcal{Hask}, \mathcal{Hask}] / F \), where \( F \) is the free group functor in \( \mathcal{Hask} \). Hence, they are defined by the natural transformations \( [\mathcal{Hask},\mathcal{Hask}](-, F) \) - i.e. toFG, or toFreeGroup.

Minimal complete definition

goldMap | toFG

Methods

goldMap :: Group g => (a -> g) -> t a -> g Source #

Apply a Group fold to some container.

This function takes a container that can be represented as a FreeGroup, and simplifies the container as a word in the free group, producing a final output according to some mapping of elements into the target group.

The name is a pun on Group and fold.

Examples:

>>> let x = FreeGroup $ [Left (1 :: Sum Word8), Left 2, Right 2, Right 3]
>>> goldMap id x
Sum {getSum = 2}

>>> goldMap (\a -> if a < 2 then mempty else a) x
Sum {getSum = 3}

toFG :: t a -> FG a Source #

Translate a GroupFoldable container into a Church-encoded free group.

Analagous to toList for Foldable, if toList respected the associativity of ⊥.

Instances

Instances details

GroupFoldable Identity Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> Identity a -> g Source # toFG :: Identity a -> FG a Source #
GroupFoldable Dual Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> Dual a -> g Source # toFG :: Dual a -> FG a Source #
GroupFoldable Sum Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> Sum a -> g Source # toFG :: Sum a -> FG a Source #
GroupFoldable Product Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> Product a -> g Source # toFG :: Product a -> FG a Source #
GroupFoldable Abelianizer Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> Abelianizer a -> g Source # toFG :: Abelianizer a -> FG a Source #
GroupFoldable FreeGroup Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> FreeGroup a -> g Source # toFG :: FreeGroup a -> FG a Source #
GroupFoldable FG Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> FG a -> g Source # toFG :: FG a -> FG a Source #
GroupFoldable (Const a :: Type -> Type) Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a0 -> g) -> Const a a0 -> g Source # toFG :: Const a a0 -> FG a0 Source #
(GroupFoldable f, GroupFoldable g) => GroupFoldable (f :+: g) Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g0 => (a -> g0) -> (f :+: g) a -> g0 Source # toFG :: (f :+: g) a -> FG a Source #
(GroupFoldable f, GroupFoldable g) => GroupFoldable (f :*: g) Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g0 => (a -> g0) -> (f :: g) a -> g0 Source # toFG :: (f :: g) a -> FG a Source #
(GroupFoldable f, GroupFoldable g) => GroupFoldable (f :.: g) Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g0 => (a -> g0) -> (f :.: g) a -> g0 Source # toFG :: (f :.: g) a -> FG a Source #
(GroupFoldable f, GroupFoldable g) => GroupFoldable (Compose f g) Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g0 => (a -> g0) -> Compose f g a -> g0 Source # toFG :: Compose f g a -> FG a Source #

Group foldable combinators

gold :: (GroupFoldable t, Group g) => t g -> g Source #

Simplify a word in GroupFoldable container as a word in a FreeGroup.

The name is a pun on Group and fold.

Examples:

>>> let x = FreeGroup $ [Left (1 :: Sum Word8), Left 2, Right 2, Right 3]
>>> gold x
Sum {getSum = 2}

goldr :: GroupFoldable t => Group g => (a -> Permutation g) -> t a -> Permutation g Source #

A right group fold from a GroupFoldable container to its permutation group

Analogous to foldr for monoidal Foldables.

toFreeGroup :: (GroupFoldable t, Group g) => t g -> FreeGroup g Source #

Convert a GroupFoldable container into a FreeGroup