Skip to content

Instantly share code, notes, and snippets.

@jpivarski

jpivarski/awkward_union_array_simplification.ipynb

Created February 10, 2023 22:00
Show Gist options
  • Save jpivarski/ea00b9269fc77b0c9b8aa7da6111ed62 to your computer and use it in GitHub Desktop.
Save jpivarski/ea00b9269fc77b0c9b8aa7da6111ed62 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
awkward_union_array_simplification.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "44d378b7-8a58-4269-b2ca-0eff93120133",
"metadata": {},
"source": [
"## What simplification rules do we need to apply to Awkward UnionArrays?\n",
"\n",
"The goal of this notebook is to see if we're missing any equivalences among combinations of the following type generators:\n",
"\n",
" * primitive types, such as unit/null, booleans, and integers\n",
" * list types, which contains another type (and `list[X] != X`)\n",
" * union types, whose instance values are one of a set (unordered) of possibilities\n",
"\n",
"The procedure is brute-force. We explore the space of composed types (down to depth 3, but only depth 2 for unions of 3 contents) and generate sample sequences. The sequences are generated in such a way that distinct types have distinct sequences, so we can find equivalence classes of type compositions. Then we apply some rules to rewrite type compositions into a canonical form, and each equivalence class should have exactly one canonical form.\n",
"\n",
"Records are not included in the set of type generators because records always create distinctions: `record[X] != X`, `record[X, Y] != record[Y, X]`, `record[X, record[Y, Z]] != record[X, Y, Z]`, etc."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "91429ea7-eabe-4fa3-99e0-dc98b79f46d9",
"metadata": {},
"outputs": [],
"source": [
"import itertools"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "ce6757f7-ad53-48a8-bfe5-b2f5e194a855",
"metadata": {},
"outputs": [],
"source": [
"class Type:\n",
" def __repr__(self):\n",
" return self.name\n",
"\n",
" def __lt__(self, other):\n",
" return self.name < other.name\n",
"\n",
" def __eq__(self, other):\n",
" return isinstance(other, Type) and self.name == other.name\n",
"\n",
" def __hash__(self):\n",
" return hash((Type, self.name))\n",
"\n",
" @property\n",
" def sequence(self):\n",
" if not hasattr(self, \"_sequence\"):\n",
" self._sequence = \" \".join(self.generate())\n",
" return self._sequence\n",
"\n",
" def equivalent(self, other):\n",
" return self.sequence == other.sequence\n",
"\n",
"\n",
"class UnitType(Type):\n",
" @property\n",
" def name(self):\n",
" return \"unit\"\n",
"\n",
" def generate(self):\n",
" yield \"null\"\n",
"\n",
"\n",
"class BooleanType(Type):\n",
" @property\n",
" def name(self):\n",
" return \"bool\"\n",
"\n",
" def generate(self):\n",
" yield \"false\"\n",
" yield \"true\"\n",
"\n",
"\n",
"class IntegerType(Type):\n",
" @property\n",
" def name(self):\n",
" return \"int\"\n",
"\n",
" def generate(self):\n",
" yield \"1\"\n",
" yield \"2\"\n",
" yield \"3\"\n",
"\n",
"\n",
"class ListType(Type):\n",
" def __init__(self, content):\n",
" self.content = content\n",
"\n",
" @property\n",
" def name(self):\n",
" return f\"list[{self.content.name}]\"\n",
"\n",
" def generate(self):\n",
" for x in self.content.generate():\n",
" yield f\"[{x}]\"\n",
"\n",
"\n",
"class UnionType(Type):\n",
" def __init__(self, *contents):\n",
" self.contents = sorted(contents)\n",
"\n",
" @property\n",
" def name(self):\n",
" return f\"union[{', '.join(x.name for x in self.contents)}]\"\n",
"\n",
" def generate(self):\n",
" out = set()\n",
" for content in self.contents:\n",
" for x in content.generate():\n",
" out.add(x)\n",
" yield from sorted(out)"
]
},
{
"cell_type": "markdown",
"id": "0cde6689-be9f-40b3-ba99-f2ee9de27e2d",
"metadata": {},
"source": [
"Verify that the sequences make the kinds of distinctions we want (only)."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "ee73c0fc-2510-4dfd-8493-2d035f5ec6a3",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'[[[1]]] [[[2]]] [[[3]]]'"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ListType(ListType(ListType(IntegerType()))).sequence"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "9799e217-3d88-4865-9aac-bb9aa8efaf7e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'[false] [null] [true]'"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"UnionType(ListType(UnitType()), ListType(BooleanType())).sequence"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "a83e974d-f933-4618-9102-f0fd68cd6425",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'[false] [null] [true]'"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ListType(UnionType(BooleanType(), UnitType())).sequence"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "9798dd21-9626-4790-b625-c8d77198d2df",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'false true'"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"UnionType(BooleanType(), BooleanType()).sequence"
]
},
{
"cell_type": "markdown",
"id": "de8239b7-a1d8-4c37-a6be-579be7043991",
"metadata": {},
"source": [
"Explore the (infinite) space of type compositions down to depth 3, but only depth 2 for unions of 3 contents (to keep the set from exploding too much).\n",
"\n",
"`count_combinations` shows that the number of combinations explored is less than 5 million."
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "f1eb3a1a-a199-4905-96bd-b2762107729e",
"metadata": {},
"outputs": [],
"source": [
"def explore(depth):\n",
" yield UnitType()\n",
" yield BooleanType()\n",
" yield IntegerType()\n",
" if depth > 0:\n",
" for c1 in explore(depth - 1):\n",
" yield ListType(c1)\n",
" for c1 in explore(depth - 1):\n",
" yield UnionType(c1)\n",
" for c1, c2 in itertools.product(explore(depth - 1), explore(depth - 1)):\n",
" yield UnionType(c1, c2)\n",
" for c1, c2, c3 in itertools.product(\n",
" explore(depth - 2), explore(depth - 2), explore(depth - 2)\n",
" ):\n",
" yield UnionType(c1, c2, c3)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "7858da22-7004-4a8a-b246-2c7c47abde90",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4696443"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def count_combinations(depth):\n",
" out = 3\n",
" if depth > 0:\n",
" num_subcombinations_1 = count_combinations(depth - 1)\n",
" num_subcombinations_2 = count_combinations(depth - 2)\n",
" out += num_subcombinations_1 # ListType(c1)\n",
" out += num_subcombinations_1 # UnionType(c1)\n",
" out += num_subcombinations_1**2 # UnionType(c1, c2)\n",
" out += num_subcombinations_2**3 # UnionType(c1, c2, c3)\n",
" return out\n",
"\n",
"\n",
"num_combinations = count_combinations(3)\n",
"num_combinations"
]
},
{
"cell_type": "markdown",
"id": "a40bd8b3-d09b-49a0-8a05-dcff9d2aa602",
"metadata": {},
"source": [
"The print-outs are a progress bar (fraction done)."
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "63143298-713b-4633-b152-eb95be3050e9",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.02129271024901186\n",
"0.04258542049802372\n",
"0.06387813074703558\n",
"0.08517084099604744\n",
"0.1064635512450593\n",
"0.12775626149407115\n",
"0.14904897174308301\n",
"0.17034168199209487\n",
"0.19163439224110673\n",
"0.2129271024901186\n",
"0.23421981273913045\n",
"0.2555125229881423\n",
"0.27680523323715417\n",
"0.29809794348616603\n",
"0.3193906537351779\n",
"0.34068336398418975\n",
"0.3619760742332016\n",
"0.38326878448221346\n",
"0.4045614947312253\n",
"0.4258542049802372\n",
"0.44714691522924904\n",
"0.4684396254782609\n",
"0.48973233572727276\n",
"0.5110250459762846\n",
"0.5323177562252964\n",
"0.5536104664743083\n",
"0.5749031767233201\n",
"0.5961958869723321\n",
"0.6174885972213439\n",
"0.6387813074703558\n",
"0.6600740177193676\n",
"0.6813667279683795\n",
"0.7026594382173913\n",
"0.7239521484664032\n",
"0.745244858715415\n",
"0.7665375689644269\n",
"0.7878302792134387\n",
"0.8091229894624506\n",
"0.8304156997114625\n",
"0.8517084099604744\n",
"0.8730011202094862\n",
"0.8942938304584981\n",
"0.9155865407075099\n",
"0.9368792509565218\n",
"0.9581719612055336\n",
"0.9794646714545455\n"
]
}
],
"source": [
"equivalence_classes = {}\n",
"\n",
"for i, t in enumerate(explore(3)):\n",
" if (i + 1) % 100000 == 0:\n",
" print((i + 1) / num_combinations)\n",
"\n",
" equivalence_class = equivalence_classes.get(t.sequence)\n",
" if equivalence_class is None:\n",
" equivalence_class = equivalence_classes[t.sequence] = []\n",
"\n",
" equivalence_class.append(t)"
]
},
{
"cell_type": "markdown",
"id": "c31e2ee5-946c-41e2-9be4-87cfbd5b8c68",
"metadata": {},
"source": [
"How many equivalence classes? How are they distributed?"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "d112f62e-026a-46ee-96b5-c93d26ebbc39",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"178"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(equivalence_classes)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "23d78e70-b22f-4002-bdfe-837bbfba9e0c",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[571,\n",
" 571,\n",
" 571,\n",
" 65,\n",
" 65,\n",
" 65,\n",
" 8,\n",
" 8,\n",
" 8,\n",
" 1,\n",
" 1,\n",
" 1,\n",
" 12,\n",
" 12,\n",
" 12,\n",
" 6,\n",
" 666,\n",
" 666,\n",
" 666,\n",
" 2640,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 20,\n",
" 36,\n",
" 36,\n",
" 36,\n",
" 24,\n",
" 36,\n",
" 36,\n",
" 36,\n",
" 24,\n",
" 36,\n",
" 36,\n",
" 36,\n",
" 24,\n",
" 82762,\n",
" 82762,\n",
" 82762,\n",
" 3196824,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 844,\n",
" 22000,\n",
" 22000,\n",
" 22000,\n",
" 275514,\n",
" 22000,\n",
" 22000,\n",
" 22000,\n",
" 275514,\n",
" 22000,\n",
" 22000,\n",
" 22000,\n",
" 275514,\n",
" 44,\n",
" 44,\n",
" 44,\n",
" 1104,\n",
" 1104,\n",
" 1104,\n",
" 1032,\n",
" 44,\n",
" 44,\n",
" 44,\n",
" 1104,\n",
" 1104,\n",
" 1104,\n",
" 1032,\n",
" 44,\n",
" 44,\n",
" 44,\n",
" 1104,\n",
" 1104,\n",
" 1104,\n",
" 1032,\n",
" 7624,\n",
" 7624,\n",
" 7624,\n",
" 30276,\n",
" 7624,\n",
" 7624,\n",
" 7624,\n",
" 30276,\n",
" 7624,\n",
" 7624,\n",
" 7624,\n",
" 30276,\n",
" 476,\n",
" 476,\n",
" 476,\n",
" 2112,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 476,\n",
" 476,\n",
" 476,\n",
" 2112,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 476,\n",
" 476,\n",
" 476,\n",
" 2112,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 16,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 32,\n",
" 32,\n",
" 32,\n",
" 24,\n",
" 4392,\n",
" 4392,\n",
" 4392,\n",
" 13824]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[len(x) for x in equivalence_classes.values()]"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "e9f5b557-1ffd-4936-a0e5-1beb31dd68bf",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sum(len(x) for x in equivalence_classes.values()) == num_combinations"
]
},
{
"cell_type": "markdown",
"id": "7f2fe182-96ee-49d3-86b3-ba4b6a5b3581",
"metadata": {},
"source": [
"These are the canonization rules:\n",
"\n",
" 1. Apply the canonization rules recursively to lists and unions.\n",
" 2. Rewrite `list[union[X, Y, ...]] → union[list[X], list[Y], ...]` (unions always go outside of lists).\n",
" 3. Rewrite `union[X, union[Y, Z, ...], ...] → union[X, Y, Z, ...]` (flatten unions of unions).\n",
" 4. Rewrite `union[X] → X` (no single-content unions).\n",
"\n",
"The assertion verifies that the rewrite rules didn't take a type _outside_ of the equivalence class (the rewritten type is the same type). It's a sanity check."
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "2d15e4f1-4ec0-4146-9be0-fb7e3ece0c3a",
"metadata": {},
"outputs": [],
"source": [
"def canonization_rules(t):\n",
" o = t\n",
"\n",
" # first pass: ensure that the canonization_rules are applied recursively\n",
" if isinstance(t, ListType):\n",
" t = ListType(canonization_rules(t.content))\n",
" elif isinstance(t, UnionType):\n",
" t = UnionType(*set(canonization_rules(c) for c in t.contents))\n",
"\n",
" # second pass: bubble unions outside of lists\n",
" if isinstance(t, ListType) and isinstance(t.content, UnionType):\n",
" t = UnionType(*set(ListType(c) for c in t.content.contents))\n",
"\n",
" # third pass: collapse unions of unions\n",
" if isinstance(t, UnionType):\n",
" contents = []\n",
" for c in t.contents:\n",
" if isinstance(c, UnionType):\n",
" contents.extend(c.contents)\n",
" else:\n",
" contents.append(c)\n",
" t = UnionType(*set(contents))\n",
"\n",
" # fourth pass: collapse unions with a single content\n",
" if isinstance(t, UnionType) and len(t.contents) == 1:\n",
" t = t.contents[0]\n",
"\n",
" assert o.sequence == t.sequence, f\"\\n{o}\\n{o.sequence}\\n\\n{t}\\n{t.sequence}\"\n",
" return t"
]
},
{
"cell_type": "markdown",
"id": "7457be43-44f6-4524-a504-ff0c5b402435",
"metadata": {},
"source": [
"The following cell applies the canonization rules to all members of each equivalence class and ensures that there is exactly one canonical type combination at the end.\n",
"\n",
"It could have been implemented with `set(canonization_rules(t) for t in equivalence_class) == 1`, but it prints this way as feedback, to help me figure out how to fix the rules when there's a problem.\n",
"\n",
"The final print-out has one line per equivalence class, the number of members of that class, and the canonical type-combination for that class. By eye, we can see that they're describing _different_ types, and the equivalence classes that have the most members are things like `union[bool, int, unit]` (imagine all of the ways that could be redundantly described)."
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "ad6d08d9-5b14-4a8f-b317-c81a630cd9be",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 571 types: unit\n",
" 571 types: bool\n",
" 571 types: int\n",
" 65 types: list[unit]\n",
" 65 types: list[bool]\n",
" 65 types: list[int]\n",
" 8 types: list[list[unit]]\n",
" 8 types: list[list[bool]]\n",
" 8 types: list[list[int]]\n",
" 1 types: list[list[list[unit]]]\n",
" 1 types: list[list[list[bool]]]\n",
" 1 types: list[list[list[int]]]\n",
" 12 types: union[list[list[bool]], list[list[unit]]]\n",
" 12 types: union[list[list[int]], list[list[unit]]]\n",
" 12 types: union[list[list[bool]], list[list[int]]]\n",
" 6 types: union[list[list[bool]], list[list[int]], list[list[unit]]]\n",
" 666 types: union[list[bool], list[unit]]\n",
" 666 types: union[list[int], list[unit]]\n",
" 666 types: union[list[bool], list[int]]\n",
" 2640 types: union[list[bool], list[int], list[unit]]\n",
" 20 types: union[list[list[unit]], list[unit]]\n",
" 20 types: union[list[list[bool]], list[unit]]\n",
" 20 types: union[list[list[int]], list[unit]]\n",
" 20 types: union[list[bool], list[list[unit]]]\n",
" 20 types: union[list[bool], list[list[bool]]]\n",
" 20 types: union[list[bool], list[list[int]]]\n",
" 20 types: union[list[int], list[list[unit]]]\n",
" 20 types: union[list[int], list[list[bool]]]\n",
" 20 types: union[list[int], list[list[int]]]\n",
" 36 types: union[list[bool], list[list[unit]], list[unit]]\n",
" 36 types: union[list[int], list[list[unit]], list[unit]]\n",
" 36 types: union[list[bool], list[int], list[list[unit]]]\n",
" 24 types: union[list[bool], list[int], list[list[unit]], list[unit]]\n",
" 36 types: union[list[bool], list[list[bool]], list[unit]]\n",
" 36 types: union[list[int], list[list[bool]], list[unit]]\n",
" 36 types: union[list[bool], list[int], list[list[bool]]]\n",
" 24 types: union[list[bool], list[int], list[list[bool]], list[unit]]\n",
" 36 types: union[list[bool], list[list[int]], list[unit]]\n",
" 36 types: union[list[int], list[list[int]], list[unit]]\n",
" 36 types: union[list[bool], list[int], list[list[int]]]\n",
" 24 types: union[list[bool], list[int], list[list[int]], list[unit]]\n",
" 82762 types: union[bool, unit]\n",
" 82762 types: union[int, unit]\n",
" 82762 types: union[bool, int]\n",
" 3196824 types: union[bool, int, unit]\n",
" 844 types: union[list[unit], unit]\n",
" 844 types: union[list[bool], unit]\n",
" 844 types: union[list[int], unit]\n",
" 844 types: union[bool, list[unit]]\n",
" 844 types: union[bool, list[bool]]\n",
" 844 types: union[bool, list[int]]\n",
" 844 types: union[int, list[unit]]\n",
" 844 types: union[int, list[bool]]\n",
" 844 types: union[int, list[int]]\n",
" 22000 types: union[bool, list[unit], unit]\n",
" 22000 types: union[int, list[unit], unit]\n",
" 22000 types: union[bool, int, list[unit]]\n",
" 275514 types: union[bool, int, list[unit], unit]\n",
" 22000 types: union[bool, list[bool], unit]\n",
" 22000 types: union[int, list[bool], unit]\n",
" 22000 types: union[bool, int, list[bool]]\n",
" 275514 types: union[bool, int, list[bool], unit]\n",
" 22000 types: union[bool, list[int], unit]\n",
" 22000 types: union[int, list[int], unit]\n",
" 22000 types: union[bool, int, list[int]]\n",
" 275514 types: union[bool, int, list[int], unit]\n",
" 44 types: union[list[list[unit]], unit]\n",
" 44 types: union[list[list[bool]], unit]\n",
" 44 types: union[list[list[int]], unit]\n",
" 1104 types: union[list[bool], list[unit], unit]\n",
" 1104 types: union[list[int], list[unit], unit]\n",
" 1104 types: union[list[bool], list[int], unit]\n",
" 1032 types: union[list[bool], list[int], list[unit], unit]\n",
" 44 types: union[bool, list[list[unit]]]\n",
" 44 types: union[bool, list[list[bool]]]\n",
" 44 types: union[bool, list[list[int]]]\n",
" 1104 types: union[bool, list[bool], list[unit]]\n",
" 1104 types: union[bool, list[int], list[unit]]\n",
" 1104 types: union[bool, list[bool], list[int]]\n",
" 1032 types: union[bool, list[bool], list[int], list[unit]]\n",
" 44 types: union[int, list[list[unit]]]\n",
" 44 types: union[int, list[list[bool]]]\n",
" 44 types: union[int, list[list[int]]]\n",
" 1104 types: union[int, list[bool], list[unit]]\n",
" 1104 types: union[int, list[int], list[unit]]\n",
" 1104 types: union[int, list[bool], list[int]]\n",
" 1032 types: union[int, list[bool], list[int], list[unit]]\n",
" 7624 types: union[bool, list[bool], list[unit], unit]\n",
" 7624 types: union[int, list[bool], list[unit], unit]\n",
" 7624 types: union[bool, int, list[bool], list[unit]]\n",
" 30276 types: union[bool, int, list[bool], list[unit], unit]\n",
" 7624 types: union[bool, list[int], list[unit], unit]\n",
" 7624 types: union[int, list[int], list[unit], unit]\n",
" 7624 types: union[bool, int, list[int], list[unit]]\n",
" 30276 types: union[bool, int, list[int], list[unit], unit]\n",
" 7624 types: union[bool, list[bool], list[int], unit]\n",
" 7624 types: union[int, list[bool], list[int], unit]\n",
" 7624 types: union[bool, int, list[bool], list[int]]\n",
" 30276 types: union[bool, int, list[bool], list[int], unit]\n",
" 476 types: union[bool, list[list[unit]], unit]\n",
" 476 types: union[int, list[list[unit]], unit]\n",
" 476 types: union[bool, int, list[list[unit]]]\n",
" 2112 types: union[bool, int, list[list[unit]], unit]\n",
" 16 types: union[list[list[unit]], list[unit], unit]\n",
" 16 types: union[list[bool], list[list[unit]], unit]\n",
" 16 types: union[list[int], list[list[unit]], unit]\n",
" 16 types: union[bool, list[list[unit]], list[unit]]\n",
" 16 types: union[bool, list[bool], list[list[unit]]]\n",
" 16 types: union[bool, list[int], list[list[unit]]]\n",
" 16 types: union[int, list[list[unit]], list[unit]]\n",
" 16 types: union[int, list[bool], list[list[unit]]]\n",
" 16 types: union[int, list[int], list[list[unit]]]\n",
" 32 types: union[bool, list[list[unit]], list[unit], unit]\n",
" 32 types: union[int, list[list[unit]], list[unit], unit]\n",
" 32 types: union[bool, int, list[list[unit]], list[unit]]\n",
" 24 types: union[bool, int, list[list[unit]], list[unit], unit]\n",
" 32 types: union[bool, list[bool], list[list[unit]], unit]\n",
" 32 types: union[int, list[bool], list[list[unit]], unit]\n",
" 32 types: union[bool, int, list[bool], list[list[unit]]]\n",
" 24 types: union[bool, int, list[bool], list[list[unit]], unit]\n",
" 32 types: union[bool, list[int], list[list[unit]], unit]\n",
" 32 types: union[int, list[int], list[list[unit]], unit]\n",
" 32 types: union[bool, int, list[int], list[list[unit]]]\n",
" 24 types: union[bool, int, list[int], list[list[unit]], unit]\n",
" 476 types: union[bool, list[list[bool]], unit]\n",
" 476 types: union[int, list[list[bool]], unit]\n",
" 476 types: union[bool, int, list[list[bool]]]\n",
" 2112 types: union[bool, int, list[list[bool]], unit]\n",
" 16 types: union[list[list[bool]], list[unit], unit]\n",
" 16 types: union[list[bool], list[list[bool]], unit]\n",
" 16 types: union[list[int], list[list[bool]], unit]\n",
" 16 types: union[bool, list[list[bool]], list[unit]]\n",
" 16 types: union[bool, list[bool], list[list[bool]]]\n",
" 16 types: union[bool, list[int], list[list[bool]]]\n",
" 16 types: union[int, list[list[bool]], list[unit]]\n",
" 16 types: union[int, list[bool], list[list[bool]]]\n",
" 16 types: union[int, list[int], list[list[bool]]]\n",
" 32 types: union[bool, list[list[bool]], list[unit], unit]\n",
" 32 types: union[int, list[list[bool]], list[unit], unit]\n",
" 32 types: union[bool, int, list[list[bool]], list[unit]]\n",
" 24 types: union[bool, int, list[list[bool]], list[unit], unit]\n",
" 32 types: union[bool, list[bool], list[list[bool]], unit]\n",
" 32 types: union[int, list[bool], list[list[bool]], unit]\n",
" 32 types: union[bool, int, list[bool], list[list[bool]]]\n",
" 24 types: union[bool, int, list[bool], list[list[bool]], unit]\n",
" 32 types: union[bool, list[int], list[list[bool]], unit]\n",
" 32 types: union[int, list[int], list[list[bool]], unit]\n",
" 32 types: union[bool, int, list[int], list[list[bool]]]\n",
" 24 types: union[bool, int, list[int], list[list[bool]], unit]\n",
" 476 types: union[bool, list[list[int]], unit]\n",
" 476 types: union[int, list[list[int]], unit]\n",
" 476 types: union[bool, int, list[list[int]]]\n",
" 2112 types: union[bool, int, list[list[int]], unit]\n",
" 16 types: union[list[list[int]], list[unit], unit]\n",
" 16 types: union[list[bool], list[list[int]], unit]\n",
" 16 types: union[list[int], list[list[int]], unit]\n",
" 16 types: union[bool, list[list[int]], list[unit]]\n",
" 16 types: union[bool, list[bool], list[list[int]]]\n",
" 16 types: union[bool, list[int], list[list[int]]]\n",
" 16 types: union[int, list[list[int]], list[unit]]\n",
" 16 types: union[int, list[bool], list[list[int]]]\n",
" 16 types: union[int, list[int], list[list[int]]]\n",
" 32 types: union[bool, list[list[int]], list[unit], unit]\n",
" 32 types: union[int, list[list[int]], list[unit], unit]\n",
" 32 types: union[bool, int, list[list[int]], list[unit]]\n",
" 24 types: union[bool, int, list[list[int]], list[unit], unit]\n",
" 32 types: union[bool, list[bool], list[list[int]], unit]\n",
" 32 types: union[int, list[bool], list[list[int]], unit]\n",
" 32 types: union[bool, int, list[bool], list[list[int]]]\n",
" 24 types: union[bool, int, list[bool], list[list[int]], unit]\n",
" 32 types: union[bool, list[int], list[list[int]], unit]\n",
" 32 types: union[int, list[int], list[list[int]], unit]\n",
" 32 types: union[bool, int, list[int], list[list[int]]]\n",
" 24 types: union[bool, int, list[int], list[list[int]], unit]\n",
" 4392 types: union[bool, list[bool], list[int], list[unit], unit]\n",
" 4392 types: union[int, list[bool], list[int], list[unit], unit]\n",
" 4392 types: union[bool, int, list[bool], list[int], list[unit]]\n",
" 13824 types: union[bool, int, list[bool], list[int], list[unit], unit]\n"
]
}
],
"source": [
"for sequence, equivalence_class in equivalence_classes.items():\n",
" print(f\"{len(equivalence_class):10d} types: \", end=\"\", flush=True)\n",
"\n",
" canonical = None\n",
" broken = False\n",
" for t in equivalence_class:\n",
" t2 = canonization_rules(t)\n",
"\n",
" if canonical is None:\n",
" print(t2)\n",
" canonical = t2\n",
" elif canonical != t2:\n",
" print(t2)\n",
" broken = True\n",
"\n",
" if broken:\n",
" break"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.15"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment