Skip to content

Instantly share code, notes, and snippets.

@kenwebb
Last active January 29, 2020 18:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kenwebb/6d048138ce60e42a800482b4c55c017c to your computer and use it in GitHub Desktop.
Save kenwebb/6d048138ce60e42a800482b4c55c017c to your computer and use it in GitHub Desktop.
progcats ps8 x1
Display the source blob
Display the rendered blob
Raw
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Wed Jan 29 2020 13:40:18 GMT-0500 (Eastern Standard Time)-->
<XholonWorkbook>
<Notes><![CDATA[
Xholon
------
Title: progcats ps8 x1
Description:
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 6d048138ce60e42a800482b4c55c017c
Keywords:
My Notes
--------
January 25, 2020
my notes from the video (Bartosz lecturing)
-----------------------
many models of the same category
are these models somehow related
are they isomorphic
we need some kind of morphisms between these models
is there a morphism in only one direction
maybe one model is very detailed and another is a very rough sketch
what would it mean to have a mapping between these two models
ex: "head" of blueprint is mapped into "head" of human
Functor F goes from "head" of blueprint to "head" of human
3:44 this also works on morphisms
ex: relation between blueprint "head" and blueprint "hand"
morphism f thru the neck and the shoulder to the head
this hand is mapped to the hand of the human in one functor
and mapped to the paw of the dog in the other functor
lift the morphism from the blueprint (from head to hand)
- to the morphism in human from head to hand F f
F acting on f
another morphism maps dog's head to its paw G f
there's also a functor G from blueprint to dog
mapping between the two models
map human head to dog head F a -> G a where a is the head
Bartosz uses different colors
KSW I use these colors in Graphviz
natural transformations
- also hand -> paw
2 models may be totally unrelated, and then there is no natural transformation
the transformation becomes natural, if it also works on morphisms
we can follow sequences of arrows/morphisms
ex: head to hand of human to paw of dog
can call the natural transformation αa (alpha a) where a is the component (head) in the blueprint
αb is alpha at b (= blueprint hand)
for every object in the blueprint
- there is a morphism between the 2 models (in this example)
at least two ways to get from human head to dog paw
hhead -> hhand -> dpaw
hhead -> dhead -> dpaw
8:40 we want the diagrams to commute
for any morphism in our source/blueprint category f: a -> b
we can go from Fa -Ff-> Fb using lifted Ff
or from Ga -Gf-> Gb using lifted Gf
called "fmap" in Haskell
f: a -> b
Ff
Fa ------> Fb
| |
αa | | αb
| |
V V
Ga ------> Gb
Gf
10:00 in Haskell
my questions include
--------------------
are there any morphisms/arrows directly between the containing category objects, for example from "blueprint" to "Human"?
is "model" a math technical term, or just something Bartosz has made up for the example
is this part of a larger math concept?
one category acts as a singleton blueprint for zero or more other possibly related categories
perhaps any category that consists just of integers and pairs can serve as a blueprint; sets + products
Bartosz uses ['a'..] rather than [1..] (expressed as Haskell lists)
Graphviz - parse and append to Xholon app
---------------------------
http://127.0.0.1:8888/XholonAntlr_DOT.html?app=progcats+ps8+x1&src=lstr&gui=clsc
run the following code in Dev Tools:
-----
var textarea = document.querySelector("textarea#xhdot");
if (textarea) {
textarea.innerText = `
digraph X { rankdir = LR
subgraph clusterB {label = Blueprint; color = indigo; style = dashed
0 1 2 3 4 5
0->1 [color = blue]
}
subgraph clusterH {label = Human; color = indigo
hhead hbody lefthand righthand leftfoot rightfoot neck shoulder
hhead->hbody [color = blue]
hhead->neck->shoulder [color = blue]
}
subgraph clusterD {label = Dog; color = indigo
dhead dbody frontleftpaw frontrightpaw backleftpaw backrightpaw
dhead->dbody [color = blue]
}
0->hhead [color = orange] [label = F]
0->dhead [color = orange] [label = G]
hhead->dhead [color = red]
}
`
}
then:
-----
then press the "Parse" button back in the application browser tab
then press the "M" key and then the "S" key, to create the d3 animation
then press the "P" key to unpause the application
we can then have the Avatar walk through this subtree
in Dev Tools:
xh.avatar().action("enter;next;enter;enter;appear");
and then use the four arrow keys back in the application browser tab
this works !
a nested Graphiv graph
-----
var textarea = document.querySelector("textarea#xhdot");
if (textarea) {
textarea.innerText = `
digraph X { rankdir = LR
subgraph clusterB {label = Blueprint; color = indigo; style = dashed
0 1 2 3 4 5
0->1 [color = blue]
}
subgraph clusterH {label = Human; color = indigo
hhead hbody lefthand righthand leftfoot rightfoot neck shoulder
hhead->hbody [color = blue]
hhead->neck->shoulder [color = blue]
subgraph clusterX {one->two->three}
}
subgraph clusterD {label = Dog; color = indigo
dhead dbody frontleftpaw frontrightpaw backleftpaw backrightpaw
dhead->dbody [color = blue]
}
0->hhead [color = orange] [label = F]
0->dhead [color = orange] [label = G]
hhead->dhead [color = red]
}
`
}
<TheSystem>
<Hello roleName="0">
<port name="edge" index="0" connector="../Hello[@roleName='1']"/>
<port name="edge" index="1" connector="../Hello[@roleName='hhead']"/>
<port name="edge" index="2" connector="../Hello[@roleName='dhead']"/>
</Hello>
<Hello roleName="1"/>
<Hello roleName="2"/>
<Hello roleName="3"/>
<Hello roleName="4"/>
<Hello roleName="5"/>
<Hello roleName="hhead">
<port name="edge" index="0" connector="../Hello[@roleName='hbody']"/>
<port name="edge" index="1" connector="../Hello[@roleName='neck']"/>
<port name="edge" index="2" connector="../Hello[@roleName='dhead']"/>
</Hello>
<Hello roleName="hbody"/>
<Hello roleName="lefthand"/>
<Hello roleName="righthand"/>
<Hello roleName="leftfoot"/>
<Hello roleName="rightfoot"/>
<Hello roleName="neck">
<port name="edge" index="0" connector="../Hello[@roleName='shoulder']"/>
</Hello>
<Hello roleName="shoulder"/>
<Hello roleName="dhead">
<port name="edge" index="0" connector="../Hello[@roleName='dbody']"/>
</Hello>
<Hello roleName="dbody"/>
<Hello roleName="frontleftpaw"/>
<Hello roleName="frontrightpaw"/>
<Hello roleName="backleftpaw"/>
<Hello roleName="backrightpaw"/>
</TheSystem>
References
----------
(1) http://brendanfong.com/programmingcats.html
(2) https://www.youtube.com/watch?v=mU3qcnBMGLw
Programming with Categories - Lecture 8
(3) https://forum.azimuthproject.org/discussion/2426/programming-with-categories-lecture-8-discussion#latest
(4) https://roamresearch.com/#/app/programming-with-categories/page/01-17-2020
davidad's notes
(5) https://gist.github.com/kenwebb/b8a7893bc4723388cd6e355069c9fd55
Programming with Categories - Shape - essence of
(6) https://github.com/kenwebb/Xholon/blob/master/Xholon/war/XholonAntlr_DOT.html
code and examples for using the antlr DOT grammar
]]></Notes>
<markdown><![CDATA[
Programming with Categories - Lecture 8 - **Blueprints and Models**
These are my notes on the first part of Bartosz' lecture.
A very simple **blueprint** for a vertebrate animal, consists of a body connected to a head at the top and four limbs along the sides, two limbs per side. Bartosz draws this as a stick figure.
~~~
O
|
--|--
|
--|--
|
~~~
There can be many models of this blueprint category. **Human** and **Dog** are two such models. The human stick figure is the stereotype of what any kindergarten kid can do - it has the same number of lines as the blueprint (6).
~~~
O
/|\
/ \
~~~
And here's my version of the dog. See the video around 2:30 to see Bartosz' much better drawing of a dog.
~~~
O-----
/\ /\
~~~
How are these models related to each other and to the blueprint? Each is a separate category.
Below are the beginnings of my program that implements this in Haskell. I am just starting to learn Haskell so this is probably very naive.
To run it, or your own version of a Haskell implementation, you can install Haskell on your computer.
Or you can visit [repl.it/languages/haskell](https://repl.it/languages/haskell), paste the following code into the editor, and click _run_.
~~~haskell
main = do
-- specify the objects in each of the three categories
let blueprint = [0..5]
let human = ["head", "body", "leftarm", "rightarm", "leftleg", "rightleg"]
let dog = ["head", "body", "frontleftpaw", "frontrightpaw", "backleftpaw", "backrightpaw"]
-- specify the morphisms from blueprint to each of the two models, using lists of pairs
let bh = zip blueprint human
let bd = zip blueprint dog
-- print out the lists of pairs (the morphisms)
print bh
print bd
~~~
The result is:
~~~
[(0,"head"),(1,"body"),(2,"leftarm"),(3,"rightarm"),(4,"leftleg"),(5,"rightleg")]
[(0,"head"),(1,"body"),(2,"frontleftpaw"),(3,"frontrightpaw"),(4,"backleftpaw"),(5,"backrightpaw")]
~~~
I will continue learning Haskell, and how it relates to Category Theory, while further exploring this example from the lecture, and invite others to do the same with this and other examples. Please feel free to make suggestions.
-----
Another way to capture Bartosz' presentation of his Blueprints and Models example, is to recreate it using Graphviz. Here's an initial version of this. Discussion and suggestions would be welcome.
~~~
digraph X { rankdir = LR
// there are three categories in the example that Bartosz presents
// each category has objects and morphisms that belong to that category
//edge {color = blue} NO
subgraph clusterB {label = Blueprint; color = indigo; style = dashed
0 1 2 3 4 5
0->1 [color = blue]
}
subgraph clusterH {label = Human; color = indigo
hhead hbody lefthand righthand leftfoot rightfoot neck shoulder
hhead->hbody [color = blue]
hhead->neck->shoulder [color = blue]
}
subgraph clusterD {label = Dog; color = indigo
dhead dbody frontleftpaw frontrightpaw backleftpaw backrightpaw
dhead->dbody [color = blue]
}
// functors between categories object -> object
0->hhead [color = orange] [label = F]
0->dhead [color = orange] [label = G]
// but Graphviz, which is based on a concept of Graph, is probably unable to completely represent functors, which include mappings between morphisms m -> m
// natural transformation, from model to model
hhead->dhead [color = red]
}
~~~
And here is the corresponding SVG image.
![Figure B](https://gist.githubusercontent.com/kenwebb/6d048138ce60e42a800482b4c55c017c/raw/c83658698c275c4e8e668a87358c34f95251d0a5/BlueprintAndModels.svg?sanitize=true "Figure B")
-----
KSW In this section, I include notes from ref[4], exported as markdown, as a test. Note that it includes latex math notation within double $ characters
- davidad's notes
- Bartosz teaching today. We are going to talk about adjunctions, which requires first refreshing the concept of natural transformations.
- ## Natural Transformations
- Consider the arrow category $$2 := \boxed{\cdot \rightarrow\cdot}$$
- And functors from $$2 \rightarrow \mathcal{C}$$
- There are many ways to find an arrow in $$\mathcal{C}$$
- Very often this second category $$\mathcal{C}$$ will be $$\mathsf{Set}$$
- The source category is a sort of "blueprint"; suppose it is a blueprint for an "animal with four things sticking out".
- We might have one functor from this into $$\mathsf{Set}$$ that looks like a human, and one that looks like a dog.
- What would it mean to have a mapping between these two models?
- For instance, the "head" in the blueprint would be mapped by the two functors $$F, G : \mathrm{Animal} \rightarrow \mathsf{Set}$$ to a human head and the head of a dog.
- But the functor also works on morphisms: there's some kind of relation between head and hand. Under one functor this is mapped to the relation between a person's head and hand, and under the other the relation between a dog's head and his paw.
- If we want to have a connection, a mapping, between these two models, then first of all we have to find a morphism in the target category between the head under $$F$$ and the head under $$G$$.
- If we call the archetypical head in $$\mathrm{Animal}$$ by the name $$a$$, this would be a morphism in $$\mathsf{Set}(Fa,Ga)$$
- A natural transformation $$\alpha : F \Rightarrow G : \mathrm{Src} \rightarrow \mathcal{C}$$ is made up of **components**. For every object $$a$$ in the source category, there is a component $$\alpha_a$$ which is a morphism $$\mathcal{C}(Fa,Ga)$$.
- ### Naturality
- All of the following are morphisms in the second category, $$\mathcal{C}$$:
- $$Ff : Fa \rightarrow Fb$$
- $$Gf : Ga \rightarrow Gb$$
- $$\alpha_a : Fa \rightarrow Ga$$
- $$\alpha_b : Fb \rightarrow Gb$$
- A condition which must be satisfied by a natural transformation, called **naturality**, is that $$Ff\, ⨾\, \alpha_b = \alpha_a\, ⨾\, Gf$$
- ### Natural Transformations in Haskell
- ```type Nat f g = forall a. f a -> g a```
- Programming intuition
- In Haskell, when you have a type constructor, the value you get will remember how it was constructed.
- There is no mutation, so it holds this value forever.
- You can determine the constructor using pattern-matching.
- In this way, an endofunctor is like a container.
- You put some stuff in when you construct it, and it stays there.
- It's like a refrigerator, keeping it fresh.
- In an imperative language, stuff will spoil, because it can mutate, but in a functional language, it always stays fresh: just as it was constructed.
- To have two functors, then, means to have two different ways of packing stuff into a container.
- Like a crate of apples and a sack or oranges.
- One way to deal with these containers is to use `fmap`: I'm going to take each apple in my crate of apples and transform them in a certain way.
- This changes the contents of a container while keeping the shape the same.
- A natural transformation is an orthogonal thing, which repacks the crate of apples into a sack, but without looking at any of the objects—only changing the shape, while keeping the contents the same.
- Naturality says that if I repackage the crate of apples into a sack and then turn them into oranges, I should get the same thing as if I turn the apples into oranges in their crate and then repackage them into a sack.
- There is parametric polymorphism in Haskell, meaning that there's a single formula that should work for all types. A polymorphic function cannot add 1 to the entries of a list, because some types do not support adding, so it is not really "`forall`" types.
- Naturality from parametric polymorphism is called a **Theorem for Free**.
- Add'l reference: "when Parametricity implies Naturality" by Uday Reddy [(pdf)](https://www.cs.bham.ac.uk/~udr/notes/naturality.pdf)
- Example: head of a list
- ```head :: [a] -> a```
- What happens when the list is empty?
- "The head will explode!"
- Your function will terminate with an error.
- This is a bad thing.
- But for performance reasons it's useful.
- Let's say we want to implement "safe head". ```head : [a] -> Maybe a```
- The idea is that if the list if empty, then we'll return `Nothing`. Now it's a total function!
- This is really a natural transformation between two functors.
- $$\mathrm{List}$$ is a functor, and $$\mathrm{Maybe}$$ is a functor (as we've seen).
- If you know how to pattern-match on a list, you can implement this. Exercise.
- Question: how does this relate to the earlier picture of natural transformation?
- For one thing, we don't have two categories in Haskell. Functors are always endofunctors $$\mathsf{Hask} \rightarrow \mathsf{Hask}$$.
- In our earlier picture, we would set $$F = \mathrm{List}$$ and $$g = \mathrm{Maybe}$$.
- $$\alpha_a$$ would correspond to the instantiation of `safe_head` on type `a`
- Question: how is an endofunctor different from a morphism, if it's operating within the same category?
- If you look at $$\mathsf{Set}$$,
- an endofunctor would, given any set, return another set;
- a morphism would have a specific domain and a specific codomain, and map elements in the domain to elements in the codomain.
- This is why it's kind of easier to imagine two categories; it removes the confusion that the mapping arrows from $$a \mapsto Fa$$ could possibly be morphisms
- Is there an identity natural transformation?
- Sure! Every component is just the identity morphisms: given $$a$$, then $$\mathrm{id}_{F a} : F a \rightarrow F a$$
- So functors between any two categories $$\mathcal{C}$$ and $$\mathcal{D}$$ form their own category! This is known as a **functor category**.
- Functors $$F,G : \mathcal{C} \rightarrow \mathcal{D}$$ form the objects of this category, and natural transformations $$\alpha : F \Rightarrow G$$ are the morphisms.
- (Switching over to Brendan teaching.)
- ### Currying
- $$\mathrm{curry} : \left( \left(a , b\right) \rightarrow c\right) \rightarrow \left(a \rightarrow \left( b \rightarrow c \right) \right)$$, and its inverse, $$\mathrm{uncurry}$$
- Why is this called currying? There was this logician Haskell Curry, whom Haskell is named after—and currying is also named after him. So it's really not a coincidence that currying is a big deal in Haskell.
- Curry's observation: if you're in a world that allows currying, you really have enough structure to interpret the $$\lambda$$-calculus.
- Say we have a category $$\mathcal{C}$$ which supports this kind of structure (products of objects and exponential objects).
- Then we have $$\mathcal{C}(a\times b, c) \cong \mathcal{C}(a, c^b)$$.
- We can view $$a \times \boxed{\cdot}$$ as a functor that maps $$x \mapsto a \times x$$, and $$c^{\boxed{\cdot}}$$ as a functor that maps $$x \mapsto c^x$$
- ## Adjunctions
- Definition
- An adjunction between categories $$\mathcal{C}$$ and $$\mathcal{A}$$ is a pair of functors $$L : \mathcal{C} \rightarrow \mathcal{A}$$ and $$R : \mathcal{A} \rightarrow \mathcal{C}$$,
- such that $$\forall c \in \mathrm{Ob}\,\mathcal{C}, a \in \mathrm{Ob}\,\mathcal{A}$$, there is an isomorphism
$$\mathcal{C}(La,c) \xrightarrow{\alpha_{a,c}} \mathcal{A}(a, Rc)$$
- where $$\alpha_{a,c}$$ is __natural in__ $$a$$ and $$c$$
- Unpacking the naturality condition
- Question: are $$La$$ and $$Rc$$ objects or are they products?
- We've been using the word "product" in almost three ways:
- The definition I gave on the board, where a product is an object $$X$$ equipped with a pair of arrows $$A \xleftarrow{\pi_1} X \xrightarrow{\pi_2} B$$
- An interpretation where we sort of forget the arrows and just think of it as the object in the middle, $$X$$
- A binary option which takes two objects and returns their product, in particular mapping $$(A, B) \mapsto X$$
- What I mean when I describe a functor as "returning a product" is really the middle version of what "product" means: "An interpretation where we sort of forget the arrows and just think of it as the object in the middle, $$X$$".
- Product adjunction
- $$\mathcal{C}(c,a)\times\mathcal{C}(c,b) \equiv \left(\mathcal{C} \times \mathcal{C}\right)\left(\left(c,c),\right(a,b)\right) \cong \mathcal{C}\left(c, a\times b \right)$$
- Coproduct adjunction
- $$\mathcal{C}(a + b, c) \cong \left(\mathcal{C} \times \mathcal{C}\right)\left(\left(a,b),\right(c,c)\right) \equiv \mathcal{C}(a,c) \times \mathcal{C}(b,c)$$
- Exponential adjunction
- $$\mathcal{C}(a \times b, c) \cong \mathcal{C}(a, c^b)$$
- Adjunctions are really cool.
- One reason is that if you compose a round-trip of two adjoint functors, you get a monad (or a comonad, if you go the other way around).
- ### Unit and counit
- Given an adjunction between $$\mathcal{C}$$ and $$\mathcal{A}$$, we can construct $$1 \xrightarrow{\mathrm{id}_{La}} \mathcal{C}(La, La) \rightarrow \mathcal{A}(a, RLa)$$
- This means for any $$a \in \mathrm{Ob}\, \mathcal{A}$$, we can obtain a morphism in $$\mathcal{A}$$ from $$a \rightarrow RLa$$.
- These morphisms form a natural transformation which we call $$\eta : \mathrm{Id} \Rightarrow RL$$, with components $$\eta_a : a \rightarrow RLa$$
- $$\eta$$ is called the **unit**.
- We can symmetrically construct a natural transformation $$\epsilon : LR \Rightarrow \mathrm{Id}$$, with components $$\varepsilon_c : LRc \rightarrow c$$ in $$\mathcal{C}$$
- $$\varepsilon$$ is called the **counit**.
- Examples:
- Product
- The counit map of this adjunction ends up with type $$(a\times b, a\times b) \rightarrow (a,b)$$
- This pulls out the projections $$\pi_1 : a\times b \rightarrow a$$, $$\pi_2 : a \times b \rightarrow b$$.
- These had seemed to be discarded in our adjunction picture, but they show up here in the counit.
- Coproduct
- The unit map of this adjunction ends up with type $$(a,b) \rightarrow (a+b, a+b)$$
- This pulls out the "coprojections" $$\mathrm{Left} : a \rightarrow a + b$$, $$\mathrm{Right} : b \rightarrow a + b$$
- Exponential
- The counit here ends up with type $$(c^b, b) \rightarrow c$$
- This is often known as $$\mathrm{eval}$$.
- Exercise: check by hand that $$\mathrm{eval}$$ is a natural transformation.
]]></markdown>
<_-.XholonClass>
<PhysicalSystem/>
</_-.XholonClass>
<xholonClassDetails>
<Avatar><Color>red</Color></Avatar>
</xholonClassDetails>
<PhysicalSystem>
</PhysicalSystem>
<PhysicalSystembehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var xhdot = $doc.querySelector("#xhdot");
if (xhdot) {
xhdot.textContent = `
// this is a sample of Graphviz DOT content
// Blueprint Human Dog
digraph X { rankdir = LR
subgraph clusterB {label = Blueprint; color = indigo; style = dashed
0 1 2 3 4 5 // a comment
0->1 [color = blue]
}
subgraph clusterH {label = Human; color = indigo
hhead hbody lefthand righthand leftfoot rightfoot neck shoulder
hhead->hbody [color = blue]
hhead->neck->shoulder [color = blue]
subgraph clusterX {label = testing; anno = "This is a Xholon annotation about X"
one [color = red]
two [color = green]
three [color = purple]
one->two->three
four [planet = <Mercury>] // an HTML_STRING
}
}
subgraph clusterD {label = Dog; color = indigo
dhead dbody frontleftpaw frontrightpaw backleftpaw backrightpaw
dhead->dbody [color = blue]
}
0->hhead [color = orange] [label = F]
0->dhead [color = orange] [label = G]
hhead->dhead [color = red]
}
`
}
$wnd.xh.avatar().action("build <Animate\tselection='#xhgraph'></Animate>; appear;");
//# sourceURL=PhysicalSystembehavior.js
]]></PhysicalSystembehavior>
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>
</XholonWorkbook>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment