# 群论笔记 07

## Table of Contents

## Cat 7.1 Functoriality, bifunctors

[lecture review]

- Functor is mappings between category;
- Endofunctor is mapping with in a category.
- Huge of functions putting together
- one major function map objects
- preserve the structure of category
- mapping between hom-sets
- if no connection will not maping; if has will not be destroyed
- preserve the composition and identity.
**object to object**— type constructor F, like List/Seq/Option- (a->b)->(Fa->Fb), F is type constructor.
- ordinaty functor = type constructor + fmap
- everything we defined for function is suit for functor, like injective and surjective
- List is function, function is list
- function is exponential datatype

### composition of functors

now functors can **composable**, and also **identity**, and also
**assoiative**.

titter :)

functors can be a category!

In **functor category*(or called category of functors) *functor** are
**morphisms**.

what is functor? he is mapping of categories. what is function? he is mapping of objects.

so, **category** is the **object** of **functor category**, so category in
functor category has another name **cat**.

tail :: [a] -> [a] //not safe for empty list

[a] is like List[A] in scala

we now learned the functor category, so we can define a `safeTail`

safeTail :: [a]->Maybe[a] safeTail [] = Nothing safeTail (x: xs) = Just xs

note that: 1. [a] is functor; Maybe[a] is functor; 2. safeTail is a mapping of functors; 3. like functor is a mapping of categories, safeTail is a functor of functor categories

seriously, :| remember `fmap`

? `fmap`

is a mapping of functions; `safeTail`

is a
mapping of functors;

we may should try using fmap

**fmap will always go inside of container(functor), and apply the operation on
the inside things, and again put it back into the container.**

seriously, :|

- now I find that, haskell has a syntax type as lisp: all operator and function are prefix, damn it.
- because function is list, and list is function. so in scala, we can apply
`fmap`

twin`map`

to`Collections`

, although the signiture of fmap is a mapping from function to function.

=haskell square on the Maybe

:: Maybe[Int] sq :: Int -> Int fmap( fmap sq ) mis // same with (fmap . fmap) sq mis // remeber that, (a->b)->(Fa-Fb) => ((a->b)->Fa) -> Fb

note that

`fmap sq`

is applying fmap to a function, you get a function >`fmap( famp sq )`

is applying fmap to the function return from**step(1)**, again get a function- funcion from
**step(2)**, takes`mis`

as parameter, operate on inside value of`mis`

getting another value, then put it back into the container.

this is how you compose the functors in haskell

we mentioned previous lecture that, almost all the type constructor in
haskell will automatically be a functor, because regular data structure
in haskell are algebraic data types, all these algebraic data types are
**automatically functorial**. And algebraic data types have some
**operations** like product(-type), sum(-type), exponential(-type).

so in algebraic datatypes' eyes, the

`Either/Option/Try/Future`

are same as`+`

in algebraic, they are both operation so in algebraic datatypes' eyes, the`collections`

are same as`*`

in algebraic, they are both operation so in algebraic datatypes' eyes, the`functions`

are same as`^`

in algebraic, they are both operation

when you use these "operaion" on algebraic datatypes, you automatically get a functor, and a 1-to-1 relationship will build up:

### Product functor

`(a,b)`

is a product-type, when can rewrite in another fomr `(,) a b`

,
and when we **fix a** ,is it a type constructor of b. Something like

type X = (,) a X b

`X`

now is a type constructor of b, a functor on b, a contrainer of b.
Now we can apply function to b, by fmap, we just illustrate it:

of couse it could do ,and the related scala code is like: a reference to type constructor used in scala's function

#### Define a functor of 2 categories by extending existing functor

Instead of definging a functor of 2 arguments — these 2 arguments are types(objects) of ONE category, can we define a functor of TWO categories: one type(object) from one category, the other (type)obj from another category.

Further more, we can define a product of two categories, then functor from the product of categories would be a functor of two arguments, of course.

But product of categories will be something too complex, even product in ONE set category would use some universal construction.

NO~~~ product of 2 categories is really easy to define, easiser than the product in set category, at least for SMALL category — which is objects in a category from sets.

small category A category C is called small if both ob(C) and hom(C) are actually sets and not proper classes, and large otherwise. A locally small category is a category such that for all objects a and b, the hom-class hom(a, b) is a set, called a homset. simply speeking, small category has two set: One set of objects, One set of arrows — hom-set.

object of product category

So we define a product category, and all objects inside are pair(or called Tuple), and is the product of the set of objects in two categories. It's easy, aren't they, because in small category, objects are in a set, so you have two category means you have two sets of objects, set can do Cartesian Product. ===> The product category has object as a pair in it.

arrow of product category

But, how to do with morphisms(arrows). This is same thing you know, becasue the small category has all arrows in a hom-set, and hom-set is set, it can also do Cartesian Product. ===> The product category has arrow as a pair in it.

proving composition

So we have new category( not prove identity, composition and identity yet), and we have objects(a pair) and arrows(a pair), Now if we can prove the composition identity associativity, then we truely have a new category, a product category

proving identity

we also have identity:

`(id, di) = id`

proving associative

easy, skipped.

we now have a product category, then we can move forward to bifunctor

#### Bifunctor

C × D ---> E

Bifunctor is just a functor for the product category, a mapping between a product category and a category. But as you know, we want a product category in Haskell, because the category is ONE category will object are type and arrow are functions, so product category is:

C × C ---> C

`C`

is the Haskell, so what we are doing for product category is:

Haskell × Haskell ---> Haskell

yes, we get it~:

a × b ---> (a,b)

#### How to define a Bifunctor

In this scenario ,we Lift two functions at same time to combine them to a pair of function, which is an arrow in new product categoy, so we can say:

class Bifunctor f where bimap :: (a->a') -> (b->b') -> (f a b -> f a' b')

`f`

is two type variable functor(or constructor), like something in
scala: `Map[_,_]`

or `Function[_,_]`

.So, product is a bifunctor.

Seriously :| By now I find that, **Functor is what we say the type
constructor with a map(which do operte unboxing and boxing) inside.**

Nothing else.

### Sum functor

Then you may think, we have **product functor** now, what about **sum
functor**?

No worries, we can use the same principle of BiFunctor, apply to sum functor.

`Either a b`

is a **sum-type**, but you should notice that we describe it
by a **BiFunctor manner**.

`Either a b`

takes a pair of types, OK pair of types is a product
category, like we have find above. Instead of every object and arrow is
**tuple pair** —

( * for object in product category: `(,) a b`

* for arrow in product
category: `(,) f g`

),

they should **eigher pair** —

( * for object in "eigther" category: `eigher a b`

* for arrow in
"eigther" category: `eigher f g`

),

in this sum-type scenario.

the ONLY difference is `fmap`

, you must use a case clause to match one
type or the other one.

### summary for `C × C -> C`

here we have two kinds of functor: product-functor and sum-functor, they
can be both decribed by `C×C->C`

— BiFunctor form.

Actually in any category, if you have products defined for all pair of
objects, like two: product-functor and sum-functor above, we have
another name for that category: **Cartesian Category**

C × C -> C , BiFunctor , Cartesian Category.

And the same is true about the **coproduct**, **coproduct is also a
BiFunctor**, long ago from now we defined coproduct just by the objects,
but now we should define the coproduct also for morphism(arrow), just
like what we do for product-functor above.

So, what we want to prove, I want to show that this is bifunctor I have
to show that I can lift this pair `(f,g)`

to something that there is a
unique morphism between `a × b`

and `a' × b'`

. But how can I do this, if
we compose f and p, compose q and g, we will find something familiar.

yes, `a × b`

become one candidate of `a' × b'`

with two projections `a'`

and `b'`

. So, there must be a unique morphism between the `a × b`

and
`a' × b'`

, we call this morphism `f × g`

and this is "but now we should
define the **coproduct also for morphism(arrow)**" — the coproduct
lifting.

### Monoidal Category 1

That is **categorical product**, not just only a **pair**, that's a
cartesian category, it's a bifunctor, and if we have a coproduct in a
category, we will have some co-Cartesian category. Then the coproduct is
a bifunctor as well. So we have a category that has a bifunctor more
general that just product or coproduct, maybe there are other
bifunctors. So this kind of category have a bifunctor are called
**monoidal category** , * **bifunctor** is like a **binary operater**. * for
**unit** we will prove that next lecture.

titter :) , monoid again, you know, unit and associative

### Some concept shoud say again:

- Product category is
`C * D -> E`

- but Product category in Haskell is just
`C * C -> C`

, — Haskell is ONE Category - So this is the same(?) thing with two arguments type constructor
- Cartesian Category is another name of Product category
- Monoidal category is that we have a bifunctor(simply speeking, two arguments type constructor) like Map[/,/] on this Cartesian category.
- bifunctor of Monidal category is that binary operator of Monoid

## Cat 7.2 Monoidal Categories,Functoriality of ADTs, Profunctors

### Monoidal category 2

we'll not introduce all things about monoidal category, it's too abstract.

In the monoidal category we would like to define things like what does it mean to multiply two objects.

product category is something like a way of multiplying objects, you have object a and object b, you multiply them and get the product.Now we have one part of a monoid — binary operation — bifuncotr.

- monoid is for set category
- binary operation is for elements of object set, or elements of hom-set.
- for production,
**unit**is singleton set`()`

, terminal object up to isomorphism.

- monoidal category is product category wih operater bifunctor.
- you can prove
**unit**from graphic below. - you also can find
**bifunctor**.

- you can prove

it means like something `F[A,Unit] = F[A]`

in scala.

I can do the same thing for coproduct, **unit would be the initial
object**

What's the good name for this product that could be a coproduct or could
be a bifunctor, it's called **tensor product**, So monoidal category has a
**tensor product**. tesor product has a unit.

#### go back to haskell

Haskell is really a monoidal category, because we had product something
in product and co-product. I start all this discussion because I said
that ADT are functorial. So far we see that the **product** is functorial
and coproduct is functorial, product type and sum type are functorial.

stop noting at 12:13

- constant type diff from type constructor ,deos not depend on type, but they depend on values ok?
- constant functor is mapping any type to a black hole.

data Const c a = Const c instance Functor(Const c)// const c is partially appplied to const c a, its a type constructor for a, a functor like 'f' before. -- fmap:: (a->b)-> Const c a -> Const c b ??? fmap f (Const c) = Const c data Identity a = Identity a fmap f (identity a) = Identity (f a)

for a container, Const c is very special, it is alwasy empty.

now we have functor, and identity, we can do composing.

if a type is ADT, it's must be a functor

data Maybe a = Nothing | Just a Either () (Identity a) // () can be Cons () a

every ADT can transform to a functor using this metohd.

{-# LANGUAGE DeriveFunctor #-} data Maybe = ...... deriving Functor

there is only one fmap(a theory can prove that, not refer deep here)

`(->) a b = a -> b`

newtype Reader c a = Reader ( c-> a) fmap = (*) // remember that? Op c a = Op (a->c) fmap::(a->b) -> Op c a -> Op c b //a->c //b->c

Is this a bifunctor above?

- a -> b
- a -> c
- b -> c // we can not get this function ???

If we have 'b->a' that's good, so a->b is bad, can we reverse?

C\^Op -> D a -> b a <-C- b

in haskell, it's a opposite haskell category to haskell This kind of
functor has a name called **Contravariant** functor.

class Contravariant f where contrmap:: (b->a) -> (fa -> fb)

Contra functor is not a container, more like a Contra-conatiner

when refer to a **bifunctor**:

(->) a b C\^op X C -> C // you take a pair morphism, but 1st is flip to another side

This is called **Profunctor**,

class Profunctor p where dimap :: (a' -> a) -> (b -> b') -> p a b -> p a' b' f g (a->b) (a' -> b') h // by f,g,h ,how to get a'->b' g * h * f

lmap ? rmap ?