Copyright | Guillaume Sabbagh 2022 |
---|---|
License | GPL-3 |
Maintainer | guillaumesabbagh@protonmail.com |
Stability | experimental |
Portability | portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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.
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
.
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 = g
:: 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.