| Copyright | Guillaume Sabbagh 2022 |
|---|---|
| License | GPL-3 |
| Maintainer | guillaumesabbagh@protonmail.com |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Math.Category
Description
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.
Synopsis
- class Morphism m o | m -> o where
- compose :: Morphism m o => [m] -> m
- class Category c m o | c -> m, m -> o where
- arWithoutId :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Set m
- isIdentity :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool
- isNotIdentity :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool
- isIso :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool
- isSection :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool
- isRetraction :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool
- areIsomorphic :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Bool
- genArWithoutId :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Set m
- isGenerator :: (Category c m o, Morphism m o, Eq m) => c -> m -> Bool
- isComposite :: (Category c m o, Morphism m o, Eq m) => c -> m -> Bool
- findInverse :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Maybe m
- findIsomorphism :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Maybe m
- findRightInverses :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Set m
- findLeftInverses :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Set m
Morphism
class Morphism m o | m -> o where Source #
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
Unsafe version of (@?).
The composition g '' f may throw an error if source g /= target f@ although it is not garanteed that it will! This is a fast function as it is not supposed to check any compatibility of morphisms.
Composition is associative :
f @ (g @ h) = (f @ g) @ h
(@?) :: Eq o => m -> m -> Maybe m Source #
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)
Return the source object of the morphism.
Return the target object of the morphism.
Instances
Morphism related functions
compose :: Morphism m o => [m] -> m Source #
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 Source #
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.
Methods
identity :: Morphism m o => c -> o -> m Source #
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 = gArguments
| :: 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 Source #
# 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] Source #
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
arWithoutId :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Set m Source #
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 Source #
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 Source #
Return wether a morphism is not an identity.
isIso :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool Source #
Return if a morphism is an isomorphism
isSection :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool Source #
Return wether a morphism is a section.
isRetraction :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> m -> Bool Source #
Return wether a morphism is a retraction.
areIsomorphic :: (Category c m o, Morphism m o, Eq m, Eq o) => c -> o -> o -> Bool Source #
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 Source #
Return the generators between two objects without the identities.
isGenerator :: (Category c m o, Morphism m o, Eq m) => c -> m -> Bool Source #
Return if a morphism is a generating morphism.
isComposite :: (Category c m o, Morphism m o, Eq m) => c -> m -> Bool Source #
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 Source #
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 Source #
Return Just an isomorphism from an object to another if possible, Nothing otherwise.