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.
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.
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).
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