Math.Category

A Morphism is composable, it has a source and a target.

A Category allows to enumerate all arrows between two objects and allows to construct the identity of an object. It is mathematically a locally finite category, we name it Category for simplicity.

See FiniteCategory for the ability to enumerate the objects of a category.

We don't reify the Category concept because we want to be able to equate categories (functions are not equatable).

A GeneratedCategory is a Category where some morphisms are selected as generators. Any Category has a trivial set of generators: the set of all of its arrows. You can override the default definition of generators when creating your Category by instantiating GeneratedCategory.

Morphism

class Morphism m o | m -> o where

A Morphism can be composed with the (@?) operator, it has a source and a target.

The (@?) operator should not be confused with the as-pattern. When using the composition operator, surround the @? symbol with spaces.

Morphism is a multiparametrized typeclass where m is the type of the morphism and o the type of the source and target objects.

Source and target are the same type of objects, we distinguish objects not by their type but instead by their values.

Methods

(@?) :: m -> m -> Maybe m

The composition g '?' f should return Nothing if source g /= target f@. This is a consequence of loosing type check at compilation time, we defer the exception handling to execution time.

Composition is associative :

(fmap (f @?)) (g @? h) = fmap (@? h) (f @? g)

source :: m -> o

Return the source object of the morphism.

target :: m -> o

Return the target object of the morphism.

Instances

Morphism HatAr HatOb

Defined in Math.FiniteCategories.Hat

Methods

(@?) :: HatAr -> HatAr -> Maybe HatAr

source :: HatAr -> HatOb

target :: HatAr -> HatOb

Morphism One One

Defined in Math.FiniteCategories.One

Methods

(@?) :: One -> One -> Maybe One

source :: One -> One

target :: One -> One

Morphism ParallelAr ParallelOb

Defined in Math.FiniteCategories.Parallel

Methods

(@?) :: ParallelAr -> ParallelAr -> Maybe ParallelAr

source :: ParallelAr -> ParallelOb

target :: ParallelAr -> ParallelOb

Morphism SquareAr SquareOb

Defined in Math.FiniteCategories.Square

Methods

(@?) :: SquareAr -> SquareAr -> Maybe SquareAr

source :: SquareAr -> SquareOb

target :: SquareAr -> SquareOb

Morphism VAr VOb

Defined in Math.FiniteCategories.V

Methods

(@?) :: VAr -> VAr -> Maybe VAr

source :: VAr -> VOb

target :: VAr -> VOb

Eq a => Morphism (StarIdentity a) a

Defined in Math.Categories.Galaxy

Methods

(@?) :: StarIdentity a -> StarIdentity a -> Maybe (StarIdentity a)

source :: StarIdentity a -> a

target :: StarIdentity a -> a

Morphism m o => Morphism (OpMorphism m) o

Defined in Math.Categories.Opposite

Methods

(@?) :: OpMorphism m -> OpMorphism m -> Maybe (OpMorphism m)

source :: OpMorphism m -> o

target :: OpMorphism m -> o

Eq a => Morphism (IsSmallerThan a) a

Defined in Math.Categories.TotalOrder

Methods

(@?) :: IsSmallerThan a -> IsSmallerThan a -> Maybe (IsSmallerThan a)

source :: IsSmallerThan a -> a

target :: IsSmallerThan a -> a

Eq a => Morphism (Function a) (Set a)

Defined in Math.Categories.FinSet

Methods

(@?) :: Function a -> Function a -> Maybe (Function a)

source :: Function a -> Set a

target :: Function a -> Set a

(Eq a, Eq b) => Morphism (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

(@?) :: CGMorphism a b -> CGMorphism a b -> Maybe (CGMorphism a b)

source :: CGMorphism a b -> a

target :: CGMorphism a b -> a

(Eq a, Eq b) => Morphism (SCGMorphism a b) a

Defined in Math.FiniteCategories.SafeCompositionGraph

Methods

(@?) :: SCGMorphism a b -> SCGMorphism a b -> Maybe (SCGMorphism a b)

source :: SCGMorphism a b -> a

target :: SCGMorphism a b -> a

(Eq n, Eq e) => Morphism (GraphHomomorphism n e) (Graph n e)

Defined in Math.Categories.FinGrph

Methods

(@?) :: GraphHomomorphism n e -> GraphHomomorphism n e -> Maybe (GraphHomomorphism n e)

source :: GraphHomomorphism n e -> Graph n e

target :: GraphHomomorphism n e -> Graph n e

(Morphism m1 o1, Morphism m2 o2, Eq o1, Eq o2, Eq m3) => Morphism (CommaMorphism o1 o2 m1 m2 m3) (CommaObject o1 o2 m3)

Defined in Math.Categories.CommaCategory

Methods

(@?) :: CommaMorphism o1 o2 m1 m2 m3 -> CommaMorphism o1 o2 m1 m2 m3 -> Maybe (CommaMorphism o1 o2 m1 m2 m3)

source :: CommaMorphism o1 o2 m1 m2 m3 -> CommaObject o1 o2 m3

target :: CommaMorphism o1 o2 m1 m2 m3 -> CommaObject o1 o2 m3

(Eq c, Eq m, Eq o) => Morphism (Diagram c m o c m o) c

Defined in Math.Categories.FinCat

Methods

(@?) :: Diagram c m o c m o -> Diagram c m o c m o -> Maybe (Diagram c m o c m o)

source :: Diagram c m o c m o -> c

target :: Diagram c m o c m o -> c

(FiniteCategory c1 m1 o1, Morphism m1 o1, Eq c1, Eq m1, Eq o1, Morphism m2 o2, Eq c2, Eq m2, Eq o2) => Morphism (NaturalTransformation c1 m1 o1 c2 m2 o2) (Diagram c1 m1 o1 c2 m2 o2)

Defined in Math.Categories.FunctorCategory

Methods

(@?) :: NaturalTransformation c1 m1 o1 c2 m2 o2 -> NaturalTransformation c1 m1 o1 c2 m2 o2 -> Maybe (NaturalTransformation c1 m1 o1 c2 m2 o2)

source :: NaturalTransformation c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2

target :: NaturalTransformation c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2

Morphism related functions

(@) :: Morphism m o => m -> m -> m

Unsafe version of (@?).

compose :: Morphism m o => [m] -> m

Return the composition of a list of morphisms.

For example : compose [f,g,h] = f @ g @ h

Return an error if the list is empty : we would have to return an identity but we don't know which one.

Category

class Category c m o | c -> m, m -> o where

A Category allows to enumerate all arrows between two objects and allows to construct the identity of an object.

A Category is multiparametrized by the type of its morphisms and the type of its objects.

This typeclass does not assume the category is finite, the number of objects in the category may be infinite.

A category is a set of objects and a set of morphisms which follows the category axioms.

A category also has sets of generating morphisms. A set of generating morphisms is a set of morphism such that every morphism of the category can be constructed by composing generators. Note that we consider identities should be generators even though they can be constructed as the composition of zero morphism because compose can't compose zero morphism.

Some algorithms are simplified because they only need to deal with generators, the rest of the properties are deduced by composition.

Every Category has at least one set of generators : the set of all of its morphisms.

You can override genAr and decompose to define a more interesting set of generating morphisms for a given Category.

Minimal complete definition

identity, ar

Methods

identity :: Morphism m o => c -> o -> m

identity should return the identity associated to the object o in the category c.

The identity morphism is a morphism such that the two following properties are verified :

f '@' 'identity' c ('source' f) = f

'identity' c ('target' g) '@' g = g

ar

Arguments

:: Morphism m o

=> c

The category

-> o

The source of the morphisms

-> o

The target of the morphisms

-> Set m

The set of morphisms in the category c between source and target

ar should return the set of all arrows between a source and a target.

Arrows with different source or target should not be equal.

genAr :: Morphism m o => c -> o -> o -> Set m

# MINIMAL identity, ar #

Same as ar but only returns the generators.

@('genAr' c s t) `isIncludedIn` ('ar' c s t)@.

The default implementation is ar because the set of all arrows generates trivially the category.

decompose :: Morphism m o => c -> m -> [m]

decompose decomposes a morphism into a list of generators (according to composition) :

m = compose (decompose c m)

An identity should be decomposed into a list containing itself.

The default implementation returns the morphism in a list as all arrows are generators.

Instances

Category Hat HatAr HatOb

Defined in Math.FiniteCategories.Hat

Methods

identity :: Hat -> HatOb -> HatAr

ar :: Hat -> HatOb -> HatOb -> Set HatAr

genAr :: Hat -> HatOb -> HatOb -> Set HatAr

decompose :: Hat -> HatAr -> [HatAr]

Category One One One

Defined in Math.FiniteCategories.One

Methods

identity :: One -> One -> One

ar :: One -> One -> One -> Set One

genAr :: One -> One -> One -> Set One

decompose :: One -> One -> [One]

Category Parallel ParallelAr ParallelOb

Defined in Math.FiniteCategories.Parallel

Methods

identity :: Parallel -> ParallelOb -> ParallelAr

ar :: Parallel -> ParallelOb -> ParallelOb -> Set ParallelAr

genAr :: Parallel -> ParallelOb -> ParallelOb -> Set ParallelAr

decompose :: Parallel -> ParallelAr -> [ParallelAr]

Category Square SquareAr SquareOb

Defined in Math.FiniteCategories.Square

Methods

identity :: Square -> SquareOb -> SquareAr

ar :: Square -> SquareOb -> SquareOb -> Set SquareAr

genAr :: Square -> SquareOb -> SquareOb -> Set SquareAr

decompose :: Square -> SquareAr -> [SquareAr]

Category V VAr VOb

Defined in Math.FiniteCategories.V

Methods

identity :: V -> VOb -> VAr

ar :: V -> VOb -> VOb -> Set VAr

genAr :: V -> VOb -> VOb -> Set VAr

decompose :: V -> VAr -> [VAr]

Eq a => Category (Galaxy a) (StarIdentity a) a

Defined in Math.Categories.Galaxy

Methods

identity :: Galaxy a -> a -> StarIdentity a

ar :: Galaxy a -> a -> a -> Set (StarIdentity a)

genAr :: Galaxy a -> a -> a -> Set (StarIdentity a)

decompose :: Galaxy a -> StarIdentity a -> [StarIdentity a]

(Category c m o, Morphism m o) => Category (Op c) (OpMorphism m) o

Defined in Math.Categories.Opposite

Methods

identity :: Op c -> o -> OpMorphism m

ar :: Op c -> o -> o -> Set (OpMorphism m)

genAr :: Op c -> o -> o -> Set (OpMorphism m)

decompose :: Op c -> OpMorphism m -> [OpMorphism m]

(Enum a, Ord a) => Category (OrdinalCategory a) (IsSmallerThan a) a

Defined in Math.Categories.OrdinalCategory

Methods

identity :: OrdinalCategory a -> a -> IsSmallerThan a

ar :: OrdinalCategory a -> a -> a -> Set (IsSmallerThan a)

genAr :: OrdinalCategory a -> a -> a -> Set (IsSmallerThan a)

decompose :: OrdinalCategory a -> IsSmallerThan a -> [IsSmallerThan a]

(Eq a, Ord a) => Category (TotalOrder a) (IsSmallerThan a) a

Defined in Math.Categories.TotalOrder

Methods

identity :: TotalOrder a -> a -> IsSmallerThan a

ar :: TotalOrder a -> a -> a -> Set (IsSmallerThan a)

genAr :: TotalOrder a -> a -> a -> Set (IsSmallerThan a)

decompose :: TotalOrder a -> IsSmallerThan a -> [IsSmallerThan a]

Eq a => Category (FinSet a) (Function a) (Set a)

Defined in Math.Categories.FinSet

Methods

identity :: FinSet a -> Set a -> Function a

ar :: FinSet a -> Set a -> Set a -> Set (Function a)

genAr :: FinSet a -> Set a -> Set a -> Set (Function a)

decompose :: FinSet a -> Function a -> [Function a]

(Eq a, Eq b) => Category (CompositionGraph a b) (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

identity :: CompositionGraph a b -> a -> CGMorphism a b

ar :: CompositionGraph a b -> a -> a -> Set (CGMorphism a b)

genAr :: CompositionGraph a b -> a -> a -> Set (CGMorphism a b)

decompose :: CompositionGraph a b -> CGMorphism a b -> [CGMorphism a b]

(Eq a, Eq b) => Category (SafeCompositionGraph a b) (SCGMorphism a b) a

Defined in Math.FiniteCategories.SafeCompositionGraph

Methods

identity :: SafeCompositionGraph a b -> a -> SCGMorphism a b

ar :: SafeCompositionGraph a b -> a -> a -> Set (SCGMorphism a b)

genAr :: SafeCompositionGraph a b -> a -> a -> Set (SCGMorphism a b)

decompose :: SafeCompositionGraph a b -> SCGMorphism a b -> [SCGMorphism a b]

(Eq n, Eq e, Show n, Show e) => Category (FinGrph n e) (GraphHomomorphism n e) (Graph n e)

Defined in Math.Categories.FinGrph

Methods

identity :: FinGrph n e -> Graph n e -> GraphHomomorphism n e

ar :: FinGrph n e -> Graph n e -> Graph n e -> Set (GraphHomomorphism n e)

genAr :: FinGrph n e -> Graph n e -> Graph n e -> Set (GraphHomomorphism n e)

decompose :: FinGrph n e -> GraphHomomorphism n e -> [GraphHomomorphism n e]

(Category c m o, Eq o) => Category (FullSubcategory c m o) m o

Defined in Math.FiniteCategories.FullSubcategory

Methods

identity :: FullSubcategory c m o -> o -> m

ar :: FullSubcategory c m o -> o -> o -> Set m

genAr :: FullSubcategory c m o -> o -> o -> Set m

decompose :: FullSubcategory c m o -> m -> [m]

(Category c m o, Eq o) => Category (InheritedFullSubcategory c m o) m o

Defined in Math.FiniteCategories.FullSubcategory

Methods

identity :: InheritedFullSubcategory c m o -> o -> m

ar :: InheritedFullSubcategory c m o -> o -> o -> Set m

genAr :: InheritedFullSubcategory c m o -> o -> o -> Set m

decompose :: InheritedFullSubcategory c m o -> m -> [m]

(Category c m o, Eq o, Eq m) => Category (InheritedSubcategory c m o) m o

Defined in Math.FiniteCategories.Subcategory

Methods

identity :: InheritedSubcategory c m o -> o -> m

ar :: InheritedSubcategory c m o -> o -> o -> Set m

genAr :: InheritedSubcategory c m o -> o -> o -> Set m

decompose :: InheritedSubcategory c m o -> m -> [m]

(Category c m o, Eq o, Eq m) => Category (Subcategory c m o) m o

Defined in Math.FiniteCategories.Subcategory

Methods

identity :: Subcategory c m o -> o -> m

ar :: Subcategory c m o -> o -> o -> Set m

genAr :: Subcategory c m o -> o -> o -> Set m

decompose :: Subcategory c m o -> m -> [m]

(FiniteCategory c m o, Morphism m o, Eq c, Eq m, Eq o) => Category (FinCat c m o) (Diagram c m o c m o) c

Defined in Math.Categories.FinCat

Methods

identity :: FinCat c m o -> c -> Diagram c m o c m o

ar :: FinCat c m o -> c -> c -> Set (Diagram c m o c m o)

genAr :: FinCat c m o -> c -> c -> Set (Diagram c m o c m o)

decompose :: FinCat c m o -> Diagram c m o c m o -> [Diagram c m o c m o]

(FiniteCategory c1 m1 o1, Morphism m1 o1, Eq c1, Eq m1, Eq o1, Category c2 m2 o2, Morphism m2 o2, Eq c2, Eq m2, Eq o2) => Category (FunctorCategory c1 m1 o1 c2 m2 o2) (NaturalTransformation c1 m1 o1 c2 m2 o2) (Diagram c1 m1 o1 c2 m2 o2)

Defined in Math.Categories.FunctorCategory

Methods

identity :: FunctorCategory c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2 -> NaturalTransformation c1 m1 o1 c2 m2 o2

ar :: FunctorCategory c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2 -> Set (NaturalTransformation c1 m1 o1 c2 m2 o2)

genAr :: FunctorCategory c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2 -> Diagram c1 m1 o1 c2 m2 o2 -> Set (NaturalTransformation c1 m1 o1 c2 m2 o2)

decompose :: FunctorCategory c1 m1 o1 c2 m2 o2 -> NaturalTransformation c1 m1 o1 c2 m2 o2 -> [NaturalTransformation c1 m1 o1 c2 m2 o2]

(Category c1 m1 o1, Morphism m1 o1, Eq m1, Eq o1, Category c2 m2 o2, Morphism m2 o2, Eq m2, Eq o2, Category c3 m3 o3, Morphism m3 o3, Eq m3, Eq o3) => Category (CommaCategory c1 m1 o1 c2 m2 o2 c3 m3 o3) (CommaMorphism o1 o2 m1 m2 m3) (CommaObject o1 o2 m3)

Defined in Math.Categories.CommaCategory

Methods

identity :: CommaCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> CommaObject o1 o2 m3 -> CommaMorphism o1 o2 m1 m2 m3

ar :: CommaCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> CommaObject o1 o2 m3 -> CommaObject o1 o2 m3 -> Set (CommaMorphism o1 o2 m1 m2 m3)

genAr :: CommaCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> CommaObject o1 o2 m3 -> CommaObject o1 o2 m3 -> Set (CommaMorphism o1 o2 m1 m2 m3)

decompose :: CommaCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> CommaMorphism o1 o2 m1 m2 m3 -> [CommaMorphism o1 o2 m1 m2 m3]

(FiniteCategory c1 m1 o1, Morphism m1 o1, Eq c1, Eq m1, Eq o1, Category c2 m2 o2, Morphism m2 o2, Eq c2, Eq m2, Eq o2, Category c3 m3 o3, Morphism m3 o3, Eq c3, Eq m3, Eq o3) => Category (PostcomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3) (NaturalTransformation c1 m1 o1 c3 m3 o3) (Diagram c1 m1 o1 c3 m3 o3)

Defined in Math.Categories.FunctorCategory

Methods

identity :: PostcomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> NaturalTransformation c1 m1 o1 c3 m3 o3

ar :: PostcomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Set (NaturalTransformation c1 m1 o1 c3 m3 o3)

genAr :: PostcomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Set (NaturalTransformation c1 m1 o1 c3 m3 o3)

decompose :: PostcomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> NaturalTransformation c1 m1 o1 c3 m3 o3 -> [NaturalTransformation c1 m1 o1 c3 m3 o3]

(FiniteCategory c1 m1 o1, Morphism m1 o1, Eq c1, Eq m1, Eq o1, FiniteCategory c2 m2 o2, Morphism m2 o2, Eq c2, Eq m2, Eq o2, Category c3 m3 o3, Morphism m3 o3, Eq c3, Eq m3, Eq o3) => Category (PrecomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3) (NaturalTransformation c1 m1 o1 c3 m3 o3) (Diagram c1 m1 o1 c3 m3 o3)

Defined in Math.Categories.FunctorCategory

Methods

identity :: PrecomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> NaturalTransformation c1 m1 o1 c3 m3 o3

ar :: PrecomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Set (NaturalTransformation c1 m1 o1 c3 m3 o3)

genAr :: PrecomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Diagram c1 m1 o1 c3 m3 o3 -> Set (NaturalTransformation c1 m1 o1 c3 m3 o3)

decompose :: PrecomposedFunctorCategory c1 m1 o1 c2 m2 o2 c3 m3 o3 -> NaturalTransformation c1 m1 o1 c3 m3 o3 -> [NaturalTransformation c1 m1 o1 c3 m3 o3]

arWithoutId :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Set m

Return the arrows between two objects without the identities.

Morphism predicates

isIdentity :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool

Return wether a morphism is an identity in a category.

isNotIdentity :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool

Return wether a morphism is not an identity.

isIso :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool

Return if a morphism is an isomorphism

isSection :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool

Return wether a morphism is a section.

isRetraction :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool

Return wether a morphism is a retraction.

areIsomorphic :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Bool

Return wether two objects are isomorphic or not.

Generator predicates

genArWithoutId :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Set m

Return the generators between two objects without the identities.

isGenerator :: (Category c m o, Morphism m o, Eq m) => c -> m -> Bool

Return if a morphism is a generating morphism.

isComposite :: (Category c m o, Morphism m o, Eq m) => c -> m -> Bool

Opposite of isGenerator, i.e. returns if the morphism is composite.

Find special morphisms

findInverse :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Maybe m

Return Just an inverse of a morphism if possible, Nothing otherwise

findIsomorphism :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Maybe m

Return Just an isomorphism from an object to another if possible, Nothing otherwise.

findRightInverses :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Set m

Find all right inverses.

findLeftInverses :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Set m

Find a left inverse if it can, returns Nothing otherwise.