Map Interface
Maps in AbstractAlgebra can be constructed from Julia functions, or they can be represented by some other kind of data, e.g. a matrix, or built up from other maps.
In the following, we will always use the word "function" to mean a Julia function, and reserve the word "map" for a map on sets, whether mathematically, or as an object in the system.
Parent objects
Maps in AbstractAlgebra currently don't have parents. This will change later when AbstractAlgebra has a category system, so that the parent of a map can be some sort of Hom set.
Map classes
All maps in AbstractAlgebra belong to a class of maps. The classes are modeled as abstract types that lie in a hierarchy, inheriting from SetMap
at the top of the hierarchy. Other classes that inherit from SetMap
are FunctionalMap
for maps that are constructed from a Julia function (or closure), and IdentityMap
for the class of the identity maps within the system.
One might naturally assume that map types belong directly to these classes in the way that types of other objects in the system belong to abstract types in the AbstractAlgebra type hierarchy. However, in order to provide an extensible system, this is not the case.
Instead, a map type MyMap
will belong to an abstract type of the form Map{D, C, T, MyMap}
, where D
is the type of the object representing the domain of the map type (this can also be an abstract type, such as Group
), C
is the type of the object representing the codomain of the map type and T
is the map class that MyMap
belongs to, e.g. SetMap
or FunctionalMap
.
Because a four parameter type system becomes quite cumbersome to use, we provide a number of functions for referring to collections of map types.
If writing a function that accepts any map type, one makes the type of its argument belong to Map
. For example f(M::Map) = 1
.
If writing a function that accepts any map from a domain of type D
to a codomain of type C
, one makes writes for example f(M::Map{D, C}) = 2
. Note that D
and C
can be abstract types, such as Group
, but otherwise must be the types of the parent objects representing the domain and codomain.
A function that accepts any map belonging to a given map class might be written as f(M::Map(FunctionalMap)) = 3
or f(M::Map(FunctionalMap){D, C}) = 4
for example, where D
and C
are the types of the parent objects for the domain and codomain.
Finally, if a function should only work for a map of a given map type MyMap
, say, one writes this f(M::Map(MyMap))
or f(M::Map(MyMap){D, C}
, where as usual D
and C
are the types of the domain and codomain parent objects.
Implementing new map types
There are two common kinds of map type that developers will need to write. The first has a fixed domain and codomain, and the second is a type parameterised by the types of the domain and codomain. We give two simple examples here of how this might look.
In the case of fixed domain and codomain, e.g. Integers{BigInt}
, we would write it as follows:
mutable struct MyMap <: Map{Integers{BigInt}, Integers{BigInt}, SetMap, MyMap}
# some data fields
end
In the case of parameterisation by the type of the domain and codomain:
mutable struct MyMap{D, C} <: Map{D, C, SetMap, MyMap}
# some data fields
end
As mentioned above, to write a function that only accepts maps of type MyMap
, one writes the functions as follows:
function my_fun(M::Map(MyMap))
The Map
function then computes the correct type to use, which is actually not MyMap
if all features of the generic Map infrastructure are required. It is bad practice to write functions for MyMap
directly instead of Map(MyMap)
, since other users will be unable to use generic constructions over the map type MyMap
.
Required functionality for maps
All map types must implement a standard interface, which we specify here.
We will define this interface for a custom map type MyMap
belonging to Map(SetMap)
, SetMap
being the map class that all maps types belong to.
Note that map types do not need to contain any specific fields, but must provide accessor functions (getters and setters) in the manner described above.
The required accessors for map types of class SetMap
are as follows.
domain(M::Map(MyMap))
codomain(M::Map(MyMap))
Return the domain and codomain parent objects respectively, for the map $M$. It is only necessary to define these functions if the map type MyMap
does not contain fields domain
and codomain
containing these parent objects.
It is also necessary to be able to apply a map. This amounts to overloading the call method for objects belonging to Map(MyMap)
.
(M::Map(MyMap)(a))
Apply the map M
to the element a
of the domain of M
. Note that it is usual to add a type assertion to the return value of this function, asserting that the return value has type elem_type(C)
where C
is the type of the codomain parent object.
Optional functionality for maps
The Generic module in AbstractAlgebra automatically provides certain functionality for map types, assuming that they satisfy the full interface described above.
However, certain map types or map classes might like to provide their own implementation of this functionality, overriding the generic functionality.
We describe this optional functionality here.
Show method
Custom map types may like to provide a custom show
method if the default of displaying the domain and codomain of the map is not sufficient.
show(io::IO, M::Map(MyMap))
Identity maps
There is a concrete map type Generic.IdentityMap{D}
for the identity map on a given domain. Here D
is the type of the object representing that domain.
Generic.IdentityMap
belongs to the supertype Map{D, C, AbstractAlgebra.IdentityMap, IdentityMap}
.
Note that the map class is also called IdentityMap
. It is an abstract type, whereas Generic.IdentityMap
is a concrete type in the Generic module.
An identity map has the property that when composed with any map whose domain or codomain is compatible, that map will be returned as the composition. Identity maps can therefore serve as a starting point when building up a composition of maps, starting an identity map.
We do not cached identity maps in the system, so that if more than one is created on the same domain, there will be more than one such map in the system. This underscores the fact that there is in general no way for the system to know if two maps compose to give an identity map, and therefore the only two maps that can be composed to give an identity map are identity maps on the same domain.
To construct an identity map for a given domain, specified by a parent object R
, say, we have the following function.
AbstractAlgebra.identity_map
— Methodidentity_map(R::D) where D <: AbstractAlgebra.Set
Return an identity map on the domain $R$.
Examples
julia> R, t = ZZ[:t]
(Univariate polynomial ring in t over integers, t)
julia> f = identity_map(R)
Identity map
of univariate polynomial ring in t over integers
julia> f(t)
t
Return an identity map on the domain $R$.
Of course there is nothing stopping a map type or class from implementing its own identity map type, and defining composition of maps of the same kind with such an identity map. In such a case, the class of such an identity map type must belong to IdentityMap
so that composition with other map types still works.
Composition of maps
Any two compatible maps in AbstractAlgebra can be composed and any composition can be applied.
In order to facilitate this, the Generic module provides a type Generic.CompositeMap{D, C}
, which contains two maps map1
and map2
, corresponding to the two maps to be applied in a composition, in the order they should be applied.
To construct a composition map from two existing maps, we have the following function:
AbstractAlgebra.compose
— Methodcompose(f::Map, g::Map)
Compose the two maps $f$ and $g$, i.e. return the map $h$ such that $h(x) = g(f(x))$.
Examples
julia> f = map_from_func(x -> x + 1, ZZ, ZZ);
julia> g = map_from_func(x -> QQ(x), ZZ, QQ);
julia> h = compose(f, g)
Functional composite map
from integers
to rationals
which is the composite of
Map: integers -> integers
Map: integers -> rationals
As a shortcut for this function we have the following operator:
*(f::Map{D, U}, g::Map{U, C}) where {D, U, C} = compose(f, g)
Note the order of composition. If we have maps $f : X \to Y$, $g : Y \to Z$ the correct order of the maps in this operator is f*g
, so that (f*g)(x) = g(f(x))
.
This is chosen so that for left $R$-module morphisms represented by a matrix, the order of matrix multiplication will match the order of composition of the corresponding morphisms.
Of course, a custom map type or class of maps can implement its own composition type and compose function.
This is the case with the FunctionalMap
class for example, which caches the Julia function/closure corresponding to the composition of two functional maps. As this cached function needs to be stored inside the composition, a special type is necessary for the composition of two functional maps.
By default, compose
will check that the two maps are composable, i.e. the codomain of the first map matches the domain of the second map. This is implemented by the following function:
check_composable(f::Map{D, U}, g::Map{U, C})
Raise an exception if the codomain of $f$ doesn't match the domain of $g$.
Note that composite maps should keep track of the two maps they were constructed from. To access these maps, the following functions are provided:
map1(f::CompositeMap)
map2(f::CompositeMap)
Any custom composite map type must also provide these functions for that map type, even if there exist fields with those names. This is because there is no common map class for all composite map types. Therefore the Generic system cannot provide fallbacks for all such composite map types.