# 群论笔记 05

## Table of Contents

## Cat 5.1 Coproducts, sum types

- today's lecture is dual work of previous lecture — coprodcut.
- Opposite Category,
**reversing the arrow**, get coproduct - similarly, monad-comonad, monoid-comonoid.

[lecture] • fix 2 object, find what it will produce. • 2 injections • like product, a very Category way: find all other objects. • then unique morphsim.

also have 2 commute triangle, differently from production, which is from fake ones to true one, this time is from the true one to fake ones

### projection vs. injection

because in right diagram, the <a,b,c,i,j> is the universal construction, he is the best, the best fit for this pattern. we want this injection, will inject the whole set, witout shrinking, without collapse anything.

we just take the whole set 'a' into the set 'c', and we do the same way with 'b'. It's the ideal match, no more, no less, just kick the edge.

### tagged union in Coproduct

#### tagged union and ordinay union

what if the 'a' and 'b' are same set? what if 'a' and 'b' have intersection? 1. the union of a set with itself, is this set itself 2. I can tag the repeated elements, and say that, although they are same elemetns, but with different tags, this is from 'a', another is from 'b'. this is called discriminated union: https://www.wikiwand.com/en/Tagged\_union

we can make c as a disjoint union, and c' as a ordinary union, but we can not reverse this, you CANNOT make c as a union and c' as a disjoint union.

**why**?

ONE element in c will map to TWO elements in c', this is NOT allowed as a function.

this is point view of Set Theory, when your union 2 sets who have duplicated elements, and these elements will keep in union result with different tags.

### product-type and sum-type

product-type | sum-type |
---|---|

Tuple(and other collection type) in scala | tagged union can only have one of the types, and with a tag |

can contain many types, like (Int,Bool) | to specify which type of the current value stored in the tagged union datatype. |

#### sum-type

data Either a b = Left a | Right b

val x: Either[Int, String] = Right("good")

These constructor directly correspond to injections, like all "**may or**"
types in scala: * Either: may this or that * Option: may value or None *
Try: may value or Exception * Future: may value(avaiable at sometime) or
Exception

## Array: `Array(Boolean, Boolean)`

* List, Seq etc.

### summarization

So, now I know that, match pattern in scala comes from Categorical Production ; and "may or" types( and you can define your own "may or" type by algebraic datatype which is pratical use of tagged union)in scala comes from the opposite thing Categorical Coprodcution. And I also know that, why "may or" types all can do pattern matching — using match case clause.

Category: product type, sum type, unit, void product-type, sum-type, unity, void are fundation of the type system. Many people said that:

In Haskell type system, half is product-type, half is sum-type, and if there is a third half, it must be the combination of them.

## Cat 5.2 Algebraic data types

### for product-type

#### production similar with monoid in 3 similar ways

we have a multiplication ,the product is similar to multiplicaiton, what
does it mean that such a multiplication? It means we have a **monoid**, at
least. **Monoid** is something **associative**, something **multiplication**,
something **unit**. But, what we want to talk about is **types**, **algebraic
data types**. Is product in the algebraic datatype has same way as
**monoid**.

remeber monoid?1.Integerform a monoid underproduction, withunity1; 2.Integerform a monoid underaddition, withunity0; 3.Stringform a monoid underconcatenation, withunityempty string 4.Listform a monoid, underappend, withunityempty list. tips ： this is why in Haskell string is list, because they are both monoid.

you can see that, all the operator who makes a set a monoid is something
like a **multiplication**, a **combination**, not a union.

so we can say a monoid have 3 attributes: 1. **unit** in set 2.
**associative** on operator 3. **combination** on view

#### symmetric up to isomorphism vs. symmetric(not related to monoid,

just show trait of isomorphism)

:CUSTOM_ID: symmetric-up-to-isomorphism-vs.symmetricnot-related-to-monoid-just-show-trait-of-isomorphism

product produce some pairs: (a,b) = (b,a) . This 2 pairs are not same, but they have same information, the only difference is just the way of encoding — Not Same, but isomorphic. We can define a function like "swap", which is a isomorphism between (a,b) and (b,a), in other words: They are not same, but same up to isomorphism.

// (a,b)!=(b,a) swap:: (a,b)->(b,a) swap p = (snd p, fst p) swap_reverse q = (snd q, fst q)

it's obvious that swap is a isomorphism between (a,b) and (b,a), so we
can say (a,b) and (b,a) is *isomorphic*

#### associative up to isomorphism vs. associative

If the production as an binary operator which under which build up a monoid, must statisfy associative rule: ((a,b),c) = (a,(b,c)). no, it's not satisfied. But they have the same information, but rearrange them, similarly we can find a function like "assoc", which is isomorphism between ((a,b),c) and (a,(b,c)), in other words: The production is not associative, but associative up to isomorphism.

// ((a,b),c) != (a,(b,c)) assoc :: ((a,b),c) -> (a,(b,c)) assoc p = <some pattern match clause> assoc_reverse q = <some pattern match clause>

vs. monid-associative for Integer under multiplication: 3/(4/5) = (3/4)/5

- production: an
**similar**-associativity on**type*(*set**) - monoid: an
**true**-associativity on**element**

#### Unit up to isomorphism vs. Unit

the same thing can apply to the unit: production dose not satisfy
`(a,()) = a`

, but they have the same information. we also can find a
function like "munit", which is a isomorphism between (a,()) and a.

// (a,()) != a munit :: (a,()) -> a munit p = fst p munit_reverse q = (q,())

vs. monid-unit for Integer under multiplication: 3*1 = 3

- production: an
**similar**-unit on**type*(*set**) - monoid: an
**true**-unit on**element**

#### production different with monoid in the way of many sets to one set

remeber monoid?1. Integer form a monoid under production, with unity 1; 2. Integer form a monoid under addition, with unity 0; 3. String form a monoid under concatenation, with unity empty string 4. List form a monoid, under append, with unity empty list. tips ： this is why in Haskell string is list, because they are both monoid.

So you can find that, monoid is just **a special set** (for unit), with
some *special operator on set*(for binary operator).

what about the product?

It's something related to many types( or we can say many sets)

product | monoid |
---|---|

type of type operate on type | a set and operat on element |

similar assoc(if isomor exist) | true assoc |

similar unit(if isomor exist) | true unit |

### for sum-type

- symmetric up to isomorphism

// Either a b ~ Either b a // easy to find a functin to do that

- associative up to isomorphism

data Triple a b c = Left a | Right c | Middle b // also easy to define a type to do that

- unit up to isomorphism

Either a void ~ a

**why not 'void' in product-type?** or **why not 'unit' in sum-type?**

def f(e: Either[Int,Unit]): Int = { e match { case Left(x) => x case Right(x) => 0 } }

// g: a => Either(a,b) // you only can get a "left" value def g(a: Int): Either[Int,Unit] = {Left(a)} // or a "right" value def g(a: Int): Either[Int,Unit] = {Right(println("0"))} // you can not get both at same time

you can see that, because the `Either`

is a **sum-type**, a "may or"
type,it's essentially a tagged union. you can never get all the value at
one time. So for **f** you can not get a **g** to make a **idendity** function
by composing them.

From another point of view, `object a <---> object Either a or unit`

*
`a=(see as a set) has *num(a)* elements; * =Either a or unit`

has
**num(a) + 1** elements;

the similar situtation for void of product-type. * ```
a=(see as a set) has
*num(a)* elements; * =Tuple(a, void)
```

has **0** elements;

**the number of values they can represet is not equall, they MUST NOT
isomorphic.**

So,*unit in product-type* and **void in sum-type**, which is just similar
to algebraic computation: * n/1=n; / n+0=n;

### why named Algebraic datatype?

By what showed in last 2 sections above, we can generalize the isomorphisms to a symbol *, whick some like the muplitply:

- a * 1 = a ; a munit () = a
- (a * b) * c = a * (b * c) ; (a,b) assoc c = a assoc (b,c)

this is why we called it that.

### we now have two monoid-like things, how to combine them.

we can now infer some formulas(which also should append with "**up to
isomorphism**", and just use symbol **~** which means **isomorphic**)

algebric computation | algebraic data types |
---|---|

a * 0 = 0 | (a,void) ~ void |

a/(b+c) = a/b+a*c | (a,Either b c) ~ Either (a,b) (a,c) |

2 = 1 + 1 | Boolean ~ Either True False |

a + 0 | Option a or None |

#### Ring

What is this structure called, both multiplication and addition in the
same thing — **ring**

A really Ring has some other things, like inversement of addition, inversement of multiplication.

If a Ring don't have all these inverse elements, it's called **semiring**
or **rig*(no spell mistake) = *Ring without negative**.

#### haskell to algebraic equation

`data List a = Nil | cons a (List a)`

It is so **self-explanatory** , and
give a **recursive** definition of `List`

> - "what is a List" > - "it's
empty or concate a value with a List"

`data List a = Nil | cons a (List a)`

In algebraic datatypes, we can find the algebraic equation:

l(a) = 1 + a * l(a) = 1 + a * (1 + a * l(a)) = ... = 1 + a + a*a + a*a*a + ...

#### algebraic equation to haskell

then, what is this `1+a+a^2+a^3+...`

, this is just what we say in
haskell

List(Nothing) | List a | List a a | List a a a | List a ... | List a_infinite

which means *all kinds of List*(has 0~infinite elements) who has the
type of element `a`

data List a = Nil | Cons a (List a)