Developers Club geek daily blog

2 years, 11 months ago
Works and koproizvedeniyeIt is the fifth article from the cycle "The Category Theory for Programmers". The previous articles were already published on Habré in transfer Monnorochof :
0. The category theory for programmers: preface
1. Category: composition essence
2. Types and functions
3. Categories, big and small
4. Kleysli's categories

On KDPV a pig Pyotr brings on one tractor to each object of category.

Follow on shooters


The Ancient Greek playwright Euripedes wrote "Any person is similar to the environment". It is right also for the category theory. It is possible to select a certain object of category only by the description of nature of its relationship with other objects (and by itself) where the relations are morphisms.

For object definition in terms of their relationship the category theory resorts to so-called universal constructions. For this purpose it is possible to select some template, the chart from objects and morphisms of a certain form and to consider all constructions of the considered category suitable under it. If the template is rather widespread and the category is rather big, then probably the found constructions will be very much and many. The idea of universal construction consists in arranging constructions under some law and to select the most suitable.

This process can be compared to net search. The request of the user is our template. If the request is not really specific, then in reply the search engine will issue a set of suitable documents, only part of which are relevant. To exclude irrelevant answers, the user specifies request that increases search accuracy. Eventually the search engine will range coincidence and if carries, the required result will be in the list head.

Initial (initial) object


The elementary template consists of the one and only object. Obviously, under it each object of category, and them very much approaches and it is a lot of. To select the most suitable, it is necessary to enter on them hierarchy. The only thing that is at our disposal, are morphisms. If to imagine morphisms as shooters, then it can turn out that from one end of category the comprehensive chain of arrows stretches to another. It is right in the arranged categories, for example, in partial orders. Let's say that the object of a precedes object of b if there is an arrow (morphism) from an in b. It would be natural to call initial object which precedes all other (i.e. from it there is an arrow in any other object of category). It is clear, what, generally speaking, initial object can not be. However what the objects satisfying to the previous determination can be more than one is much worse. How to specify our determination? The arranged categories give the hint: in them between two objects there are no more than one arrow (there is only one method to be more or less, than other object). It leads us to the following determination:
The initial object is an object from which in any object of category exactly one morphism proceeds.

Works and koproizvedeniye

Actually, even such determination does not guarantee uniqueness of initial object (if it exists). However it guarantees uniqueness about accuracy to isomorphism. Isomorphism — very important concept for the category theory, we soon will return to it.

Let's review several examples. The initial object in partially ordered set is its smallest element. Some partially ordered sets, such as all integral numbers (both positive, and negative), have no initial object.

In category of sets the initial object is an empty set. Let's remind, the empty set corresponds to type Void in Haskell (in C ++ there is no corresponding type) and the only polymorphic function from Void in any other type, called absurd:
absurd :: Void -> a

Existence of such function also does Void initial object of category of sets.

Terminal object


Let's continue experiments with a template from the only object, but we will change a ranging method. Let's say that the object of a follows object of b if there is a morphism from b in a (pay attention to change of the direction). We are interested in the latest object of category. For reasons of uniqueness we will define it so:
The terminal object is an object to which of any object of category exactly one morphism comes.

Works and koproizvedeniye

Besides terminal object edinstvenen to within isomorphism that will be soon proved. However at first we will review several examples. In partially ordered set the terminal object (if it exists) is the greatest object. In category of sets the terminal object is Singleton. Let's remind, Singleton corresponds to type void in C ++ and to type () in Haskell is also the type inhabited by exactly one value, implicit in C ++ and explicit in Haskell, designated as the same literal (). Earlier it was established that there is the only pure function from any type in ():
unit :: a -> ()
unit _ = ()

so all requirements to terminal object are fulfilled.

Let's notice that in this case the condition of uniqueness is crucial as there are also other sets (actually, all sets except empty) which have the entering morphisms from any other type. For example, there is a function with values of type Bool (predicate), defined for any type of argument:
yes :: a -> Bool
yes _ = True

However Bool is not terminal object because there is at least one more function from any type in Bool:
no :: a -> Bool
no _ = False

The requirement of uniqueness of morphisms gives us necessary accuracy, narrowing a set of suitable terminal objects to one.

Duality


It is necessary to notice symmetry between determinations of initial and terminal objects. All difference consists in the direction of morphisms. For any category C it is possible to define the dual category COP just having turned all arrows back. The dual category automatically satisfies to determination of category if we along with the address of arrows redefine composition. If composition of initial morphisms f::a->b and g::b->c was h::a->c with h=g∘f, composition of the turned morphisms f_op::b->a and g_op::c->b will be h_op::c->a with h_op=f_op∘g_op. Let's note that the address of an identical arrow matches her.

Duality is the very important property of categories doubling labor productivity of a teoretiko-kategorik. For any construction takes place dual and, having proved one theorem, you receive the second free of charge. Constructions of dual category often have a prefix "to": works and koproizvedeniye, monads and komonada, cones and kokonusa, limits and kopredela, etc. However it does not make sense to consider to-to-constructions, twice turned arrow matches with initial so, for example, kokomonada match monads.

So, the terminal object is an initial object in dual category.

Isomorphisms


Programmers well know what is not so simple to define equality. What means that two objects are equal? Do they have to occupy the same area of memory (equality of pointers)? Or it is enough of fact that values all of them a component match? Whether equal two complex numbers if one of them is set valid and imaginary by components, and another — argument and the module are considered? It would be possible to count that mathematics has sacral knowledge of equality determination, but it not so. In mathematics there is also a set of types of equality, and also weaker concept of isomorphism and weaker — equivalence.

Intuitively objects are isomorphic if they have an identical appearance, are externally indiscernible: any part of one object one-to-one corresponds to some part of other object; according to indications of measuring devices available to us objects are exact copies of each other. Mathematically it means that there are vzaimnoobratny displays from object of an in object of b and from object of b in object of a. The category theory generalizes displays to morphisms. Isomorphism is a reversible morphism or, in other words, couple of morphisms, the return to each other.

The concept of reversibility is expressed in terms of composition and single morphism: the morphism of g is the return to f if their composition is a single morphism. Actually it not one, but two conditions as there are two methods of composition of couple of morphisms:
f . g = id
g . f = id

When we say that the initial (terminal) object edinstvenen to within isomorphism, means that any two initial (terminal) objects are isomorphic. It is easy to show it. Let's assume that i1 and i2 — initial objects in the same category. As i1 initial, exists the only morphism of f from i1 in i2. Similarly, as i2 initial, exists the only morphism of g from i2 in i1. What it is possible to tell about composition of these morphisms?
Works and koproizvedeniye

The composition of g∘f has to be a morphism from i1 in i1. But i1 is initial object so there is exactly one morphism from i1 in i1 and as the beginning and the end of an arrow match, this vacancy is already busy with a single morphism. Therefore, they have to match: the morphism of g∘f is single. Similar to f∘g morphism also matches with single as there can be only one morphism from i2 in i2. Thus, f and g of a vzaimnoobratna, and two initial objects are isomorphic.

Let's notice that our proof of uniqueness of initial object to within isomorphism significantly used uniqueness of a morphism from initial object in itself. However whether the fact that morphisms of f and g also edinstvenna is important? The matter is that actually we proved more strict statement: initial object edinstvenen to within the only isomorphism. Generally speaking, between two objects there can be more than one isomorphism, but not in this case. "Uniqueness to within the only isomorphism" — important property of all universal constructions.

Works


The following universal construction is a work. We are already familiar with Cartesian the work of two sets consisting of a set of all possible couples. What template connects quotient-set with sets multipliers? If we reveal it, then we will be able to generalize concept of work on other categories.

With Cartesian work connected two functions (projectors) operating from a set work in the corresponding set multiplier. In Haskell these functions are called fst and snd also select the first and second elements of couple respectively:
fst :: (a, b) -> a
fst (x, y) = x
snd :: (a, b) -> b
snd (x, y) = y

Here functions are defined by means of comparison of argument to a sample: the sample corresponds to any couple (x, y) also selects its components in variables x and y.

These determinations can be simplified by means of crossed out sections:
fst (x, _) = x
snd (_, y) = y

In C ++ we will use sample functions, for example:
template<class A, class B>
A fst(pair<A, B> const & p) {
    return p.first;
}

By means of this (seeming scanty) information on work we will try to design the template corresponding to it from objects and morphisms in category of sets. This template will consist of objects multipliers of an and b, C object and the projecting morphisms of p and q:
p :: c -> a
q :: c -> b

Works and koproizvedeniye

All C objects which satisfy to such template will be considered as candidates for work. Such objects can be much.
Works and koproizvedeniye

For an example we will take two types as multipliers, namely Int and Bool, we will also consider selection of candidates for their work.

Here the first of them: Int. Whether can Int to be considered as the candidate for work Int and Bool? Yes, can, the projectors here corresponding:
p :: Int -> Int
p x = x

q :: Int -> Bool
q _ = True

Looks suspiciously, but quite corresponds to a template.

Here still candidate: (Int, Int, Bool). It is a train from three elements. Here the corresponding couple of projecting morphisms (we use pattern matching again):
p :: (Int, Int, Bool) -> Int
p (x, _, _) = x

q :: (Int, Int, Bool) -> Bool
q (_, _, b) = b

The attentive reader could notice that the first candidate is too small — he covers only Int- to a work component, and the second is too big because it includes obviously dummy Int- to a component.

We meanwhile considered only the first component of universal construction — a template, but told nothing about the second — about ranging. We need the method allowing to compare two candidates corresponding to a template namely C object to projectors of p and q and C object' to p projectors' and q'. It would be desirable to put that with better with' if there is m morphism from with' in c, but this too weak condition. It is necessary also demand that projectors of p and q were better (more universally), than p' and q'. It means that p' and q' can be recovered on p and q by means of m:
p’ = p . m
q’ = q . m

Works and koproizvedeniye

Number theory specialist would tell that m is a divider (factor) of p' and q'. Imagine natural numbers instead of morphisms and multiplication instead of composition: then m will be a common divisor of p' and q'. Further in similar situations we will say that m factorizes p' and q'.

For training of intuition we will show that couple (Int, Bool) with two canonical projectors fst and snd it is certain better, than the candidates considered above.
Works and koproizvedeniye

Display m for the first candidate has an appearance:
m :: Int -> (Int, Bool)
m x = (x, True)

Really, both projectors p and q can be recovered as:
p x = fst (m x) = x
q x = snd (m x) = True

Morphism m for the second example it is also defined uniquely:
m (x, _, b) = (x, b)

We showed that (Int, Bool) it is better than both candidates. Let's show that the return is incorrect. Whether it is possible to find some morphism m', which will allow to recover fst and snd on p and q?
fst = p . m’
snd = q . m’

In the first example q always returns True, however at the same time there are couples in which acts as the second component False. So to recover snd on q it is impossible.

In the second example the situation is differently: we have enough information later p and q, to recover fst and snd, however the factorizing morphism m' it is defined ambiguously. Really, as and p, and q ignore the second element of a train, a morphism m' can place anything there:
m’ (x, b) = (x, x, b)

or
m’ (x, b) = (x, 42, b)

etc.

Summing up the aforesaid, for this type c with projectors p and q there is the only morphism m from c in the Cartesian product (a, b), which factorizes p and q. Actually m just combines them in couple:
m :: c -> (a, b)
m x = (p x, q x)

It does the Cartesian product (a, b) the best candidate also completes consideration of this universal construction for category of sets.

Now we will forget about sets and we will define work of two objects in any category by means of the same universal construction. Such work (if exists) only to within the only isomorphism.
Work of objects of an and b is the such C object equipped with two projectors that for any other C object equipped with projectors' there is the only morphism of m from with' in c factorizing these projectors.

Function (higher order) which builds the factorizing morphism on two projectors sometimes is called a faktorizator. In our case it has an appearance:
factorizer :: (c -> a) -> (c -> b) -> (c -> (a, b))
factorizer p q = \x -> (p x, q x)

Koproizvedeniya


As well as any construction of the category theory, work has the double called by a koproizvedeniye. If we turn arrows in a work template, then we will receive the C object equipped with two attachments i and j, morphisms from an and b in with.
i :: a -> c
j :: b -> c

Works and koproizvedeniye

We also should turn a ranging order: now the C object will be considered better than C object', i equipped with attachments' and j' if there is m morphism from with in with', factorizing attachments:
i&39; = m . i
j&39; = m . j

Works and koproizvedeniye

The best of such objects possessing the only morphism in all other objects answering to a template is called a koproizvedeniye and if exists, edinstvenen to within the only isomorphism.
Koproizvedeniye of objects of an and b is the such C object equipped with two attachments that for any other C object equipped with attachments' there is the only morphism of m from with in with', factorizing these attachments.

In category of sets the koproizvedeniye is a disjoint union. The element of disjoint union of an and b is either an element a, or an element b. If two sets are crossed, then disjoint union contains both copies of a common part. It is possible to consider that elements of disjoint union are marked with tags of sets sources.

For the programmer the koproizvedeniye is the marked consolidation of two types. ++ supports by C not marked associations; the problem of tracking what of members of consolidation is valid lies on the programmer's shoulders. To create the marked consolidation it is necessary to define a tag — transfer — and to combine it with consolidation. For example, the marked consolidation int and char const * can look so:
struct Contact {
    enum { isPhone, isEmail } tag;
    union { int phoneNum; char const * emailAddr; };
};

Two attachments can be implemented either as designers, or as functions. For example, here the first attachment in the form of function PhoneNum:
Contact PhoneNum(int n) {
    Contact c;
    c.tag = isPhone;
    c.phoneNum = n;
    return c;
}

This function puts int in Contact.

The marked consolidation is also called variant, which generalized implementation is in boost library (boost::variant).

In Haskell it is possible to make the marked consolidation of any data types, separating designers vertical line. Considered above Contact registers so:
data Contact = PhoneNum Int | EmailAddr String

Here PhoneNum and EmailAddr act also as designers (attachments) and as tags for pattern matching (see below). For example, here it is so possible to construct Contact on telephone number:
helpdesk :: Contact;
helpdesk = PhoneNum 2222222

Unlike the canonical implementation of work which is built in syntax of Haskell as primitive couple, canonical implementation of a koproizvedeniye is not special language construction, but ordinary data type Either from standard library:
Either a b = Left a | Right b

This data type is parametrized by two types a and b also two designers have: Left, accepting type a, and Right, accepting type b.

By analogy with a faktorizator for work it is possible to define also a faktorizator for a koproizvedeniye. For this candidate for koproizvedeniye in the form of type c with two attachments i and j let's construct the factorizing morphism:
factorizer :: (a -> c) -> (b -> c) -> Either a b -> c
factorizer i j (Left a)  = i a
factorizer i j (Right b) = j b

Asymmetry


Above we considered two couples of dual determinations: first, determination of terminal object can be received from determination of initial object by the address of arrows, secondly, in the same way determination of a koproizvedeniye from work determination turns out. However in category of sets the initial object essentially differs from terminal, and a koproizvedeniye — from work. It will be shown below that work behaves as multiplication with the terminal object playing unit role, and the koproizvedeniye is similar to addition where instead of zero — initial object. In particular, for finite sets the quantity of elements of work are work of quantities of elements in initial sets, and the quantity of elements of a koproizvedeniye is equal to the sum of initial quantities.

It shows that the category of sets is not symmetric concerning the address of arrows.

Let's notice that in spite of the fact that the only arrow in any other set proceeds from empty set (function absurd), there is no morphism entering it. Singleton (a set from one element) has not only the only arrow entering him from any set but also outgoing arrows in each non-blank set. As we saw earlier, these shooters proceeding from terminal object play an important role in the choice of elements of other sets (in empty set there are no elements so there is nothing and to select).

The relationship with Singleton is in what work differs from a koproizvedeniye. Let's consider Singleton consisting of one element () as the object answering to a work template. Let's equip it with two projectors: let p and q — functions from Singleton in each of a work component. Both of them select fixed members in the corresponding sets. As work is universal, there is (only) morphism m from Singleton in work. This morphism selects an element from a set of work, i.e. the fixed couple, and factorizes projectors:
p = fst . m
q = snd . m

If to substitute the only element of Singleton in these equations (), we will receive:
p () = fst (m ())
q () = snd (m ())

As m () — it is the work element selected by a morphism m, these equations mean that an element p (), selected by a projector p from the first set, is the first komponenty couple selected m. Similarly, q () the second is equal a component. It will completely be approved with treatment of elements of a set work as steam of elements from sets multipliers.

However for a koproizvedeniye of such simple interpretation does not exist. It is possible to try to consider Singleton as candidate for koproizvedeniye, trying to isolate from him elements, but in that case we will receive two entering attachments, but not two outgoing projectors. Attachments tell nothing about the sources (actually as we saw earlier, in case of Singleton they with need ignore the argument). The same concerns also the only morphism from a koproizvedeniye in Singleton. The view of category of sets from initial object (on shooters) is absolutely other than a view from the party of terminal object (against arrows).

The specified distinction is not specific property actually of sets; this property of functions which act as morphisms of category of sets of Set. Functions are inherently asymmetric. Let's consider this moment in more detail.

Function has to be defined for each element of the definition range (in programming such function is called total), but is not obliged to cover area of values entirely. For example, functions from Singleton get to only one element from area of values. A degenerate case are functions from empty set — they do not accept any of values at all. In an opposite situation when function values cover all available values, function is called surjective.

One more source of asymmetry is that function can stick together many elements from definition range in one element from area of values. For example, functions in Singleton stick together all elements of an initial set in one (). Above polymorphic function was considered unit. If under the influence of function images of all elements are different, then function is called injective.

Of course there are functions which are good in both relations, i.e. are both surjective, and injective. They are called bijections and as are reversible, form symmetric communication between definition range and area of values. In category of sets isomorphism is the same as bijection.

Exercises


  1. Show that terminal object edinstvenen to within the only isomorphism.
  2. What represents work in partially ordered set? Hint: use universal construction.
  3. What represents a koproizvedeniye in partially ordered set?
  4. Implement analog Either from Haskell in your favourite programming language (but not on Haskell).
  5. Show that Either is more suitable koproizvedeniye, than int, equipped with two attachments:
    int i(int n)  { return n; }
    int j(bool b) { return b ? 0 : 1; }

    Hint: define function
    int m(Either const & e);

    which factorizes i and j.
  6. Reason (continuation) why int with two attachments i and j cannot be more preferable Either?
  7. (Continuation) As about such attachments?
    int i(int n) {
        if (n < 0) return n;
        return n + 2;
    }
    int j(bool b) { return b ? 0 : 1; }
  8. Offer the unsuccessful candidate for koproizvedeniye for int and bool, which will be worse Either what allows several morphisms in Either.

Literature


The Catsters, Products and Coproducts video.

Thanks


The author is grateful Gershoma Bazermana for reviewing of a post before the publication and fruitful discussions.

This article is a translation of the original post at habrahabr.ru/post/271927/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus