Python Dict category

Python uses a dictionary, and I'm a little wondering if the key isn't a string, but the dictionary is a bit different, but I think it's overwhelmingly better than Hash. In terms of the correspondence between the case elements of the value group and the key group, it seems mathematically correct to call it a function, but it also causes confusion. https://twitter.com/shibu_jp/status/471445247973527553

Well, I feel that map is the safest. https://twitter.com/shibu_jp/status/471445639964815360

A Python dictionary is a set of key and value pairs, for example {'a': 10,'b': 20}, but of course this dict is a mapping (because it is not defined for the entire String in this example. It is not a function). However, I wondered if I could call this morphism somehow, so I thought about it in various ways and summarized it.

Since I thought about it without permission, the following may contain serious mistakes. If you find one, please point it out in the comments.

Dict area

In the following, we will consider a set of instances of Python's built-in class when we call it a type, and will not consider other instances (such as self-made classes) for the time being. The key and value types of the dictionary are fixed. That is, the set of key and value is a standard Python type (Bool, Int, Str, [Int], ...), and there is only one type. .. Dictionaries with key of type $ A $ and value of type $ B $ are naturally equated with these Cartesian product subsets, and dictionaries can also be considered as subgraphs of the map $ A \ to B $. is there.

At this time, the following is called ** Dict area **.

--Target: Python type --Morphism: $ f: X \ to Y $ is a morphism in the Dict category, $ f $ is a dictionary with $ X $ as the key and $ Y $ as the value. --Synthesis of morphisms: $ f: X \ to Y $, $ g: Y \ to Z $, $ g \ circ f: X \ to Z = [(x, z); \ exists y: It is defined as (x, y) \ in f, (y, z) \ in g] $. This is a dictionary that synthesizes and collects values that can be synthesized.

It naturally has a category structure. For any object $ X $, $ 1_X = [(x, x); x \ in X] $ (this is a graph of the identity map $ X \ to X $ as a map. Is an identity morphism.

nature

Let $ A, B $ be the type and $ f, g: A \ rightrightarrows B $ be the parallel morphism. At this time, the following is clear.

--terminal object: If terminal object exists, it is a type that has no element such as N = {}. At this time, a unique morphism {} from any type extends. --product: $ A \ times B $ is a direct product as a set. In Python this is defined as a tuple of A and B. $ p_A = [((a, b), a); a \ in A, b \ in B]: A \ times B \ to A $ is a morphism, and for any object and morphism pair $ Z, z_A, z_B $, the morphism $ h $ derived from UMP is $ h = [(z, (a, b)); \ exists z. (Z, a) \ in z_A, (z, b) \ in z_B \ wedge \ exists z. (Z, a) \ in z_A, b \ in B \ wedge \ exists z. (Z, b) \ in z_B, a \ in A] $. (This $ h $ is the sum of the set at $ z_A $ and the set at $ z_B $. However, if there are pairs for the common $ z $, those pairs are made to correspond, and if they do not exist, it is created by appropriately fetching from $ A and B $. Is a morphism that makes the diagram convertible.) --equalizer: $ f, g $ equalizer $ (E, e: E \ to A) $ is $ E = [a \ in A; \ exists v: (a, v) \ in f, (a, v) \ in g] $, $ e = [(a, a); a \ in E] $.

The product and equalizer can be configured in the same way as Set. However, the dictionary words are used here to describe the morphism. The existence of pullback is guaranteed by the following.

Fact. Category $ \ mathscr {C} $ has a finite limit if it has a terminal object, binary product, equalizer.

Therefore, it was found that the Dict category has a finite limit.

--exponential: $ Z ^ X $ is the entire morphism from $ X $ to $ Z $. Then evaluation is a dictionary like this: $ e = [((f, x), z); \ exists (x, z) \ in f] $. That is, for $ f $ and $ x $, if $ f (x) $ exists, it will be $ (f, x) \ mapsto f (x) $. The evaluation arrow is a collection of all such correspondences. At this time, for $ f: Y \ times X \ to Z $, the morphism $ h $ derived from UMP is $ h = [ (y, [(x, z)]); ((y, x), z) \ in f] $.

Therefore, the Dict category is CCC (Cartesian Closed Category).

comment

It was interesting to be able to configure it with the same feeling as $ \ mathbf {Set} $, but there were many images that could not be immediately understood without confirming that it exists universally and becomes commutative. Also, I wonder if this category (the same category as) has no name. Also, I don't do it because it's troublesome, but I feel that I can show that it is elementary to pos. It's an exercise (appropriate).

Summary: Don't call a Python dict a morphism because it's more confusing. Also, at least it's not a map.

Recommended Posts

Python Dict category
Python
How Python __dict__ is used
Python basic dict sort order
Use list-keyed dict in Python
python dict object memorandum (mysterious document)
About python dict and sorted functions
python / Make a dict from a list.
Make Python dict accessible by Attribute
kafka python
Python basics ⑤
python + lottery 6
Python Summary
Built-in python
Python comprehension
Studying python
Python 2.7 Countdown
Python memorandum
Python> dir ({})> dict Returns the object's attributes
Python FlowFishMaster
Python service
python tips
Python memo
Python comprehension
Python Singleton
Python> empty XXX (XXX: dict, list, tuple, set)> {} / [] / () / set ()
Python basics ④
Python Memorandum 2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Try python
Python memo
Python 3.9 dict merge (`|`) seems to be useful
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
python underscore
Python summary
Start python
[Python] Sort
Note: Python
Python basics ③
python log
Python basics
python memo
Python memorandum
Python # sort
ufo-> python
Python nslookup
python learning
Hannari Python 2020
[Rpmbuild] Python 3.7.3.