{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Monoids for Pythonistas\n",
"\n",
"[Bartosz Milewsky](https://bartoszmilewski.com/) has a great series of articles on category theory as it applies to programmers.\n",
"I'm not going to lie, the material is pretty dense which is par for the course for a lot of mathematics subjects (maybe it's worth mentioning that Bartosz has a PhD in Theoretical Physics ðŸ˜¬).\n",
"However, many of the core concepts are reasonably simple abstractions, and programmers know all about abstractions!\n",
"The language can be as big a hurdle as reading mathematics symbols, but these are the tools mathematicians use to convey ideas in an elegant and concise way.\n",
"\n",
"I promise that you know what monoids are - you use them every day as a programmer!\n",
"I am going to flip the script and try to work my way to the definition instead of the other way around.\n",
"Hopefully, with a bit of patience, we can uncover the power of these ideas and see how they apply to our day-to-day jobs!\n",
"\n",
"**Disclaimer** This is not meant to be a mathematically rigorous discussion. Many small details are overlooked in favor of a high-level understanding. However, please make me aware of any egregious offenses!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sets\n",
"\n",
"As a programmer, you _should_ know what a set is - an unordered collection of unique items of the same type (and if not, maybe a blog post for another day!).\n",
"\n",
"```python\n",
">>> my_pets = {\"Lamby\", \"Dozer\", \"Onyx\", \"BlackHen\", \"RedHen\", \"NoisyRooster\"}\n",
">>> my_pets.add(\"BuffHen\")\n",
">>> \"Frank\" in my_pets\n",
"False\n",
">>> my_pets.add(\"BuffHen\") # `add` is idempotent and won't create a duplicate\n",
">>> my_pets # Notice that the order isn't consistent\n",
"{'NoisyRooster', 'RedHen', 'BuffHen', 'BlackHen', 'Lamby', 'Onyx', 'Dozer'}\n",
">>>\n",
">>> pets_son_feeds = {\"Shayna\", \"Lamby\"}\n",
">>> pets_son_feeds.intersection(my_pets)\n",
"{'Lamby'}\n",
">>>\n",
"```\n",
"\n",
"The integers form a set, $\\mathbb{I} = \\{-1,0,1,2,3,4...\\}$.\n",
"Rational numbers form a set, $\\mathbb{Q} = \\{-99.42,0,1.1,1.2,1.3...\\}$.\n",
"Character strings even form a set, $\\{\\text{\"a\", \"b\", \"c\", \"foo\", \"cow\", \"Bob\", ...}\\}$.\n",
"For the purposes of this article, a \"set\" is a mathematical set, not constrained by physical memory limits of computers."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Symbols\n",
"\n",
"Symbols are the syntax of mathematics.\n",
"\n",
"### $\\forall$\n",
"\n",
"Means \"for all\". Given a set, \"_for every element_ in the set.\" In the definition of a monoid, we will use this to assert a property of the items in the set. It is somewhat analogous to a `for` loop over all the items.\n",
"\n",
"```python\n",
">>> odds = {1, 3, 5, 7, 9}\n",
">>> for odd in odds: # âˆ€ in the set...\n",
"... assert odd % 2 == 1 # Assert that an odd divided by 2 has a remainder of 1\n",
"...\n",
">>> # Success!\n",
"```\n",
"\n",
"### $\\in$\n",
"\n",
"means \"in\" or \"an element of\". 1 is _an element of_ the set of integers.\n",
"\n",
"```python\n",
">>> some_primes = {2, 3, 5, 7, 11}\n",
">>> 7 in some_primes # 7 âˆˆ some_primes == True\n",
"True\n",
">>>\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## More terminology\n",
"\n",
"### Binary operation\n",
"\n",
"An operation that works on two (hence binary) values; addition, multiplication, division, etc. Most of the Python numeric [dunder methods](https://docs.python.org/3/reference/datamodel.html#emulating-numeric-types) are binary operations.\n",
"\n",
"### Associative\n",
"\n",
"If an operation is associative, the order of _composition_ doesn't matter.\n",
"This property is **very** important as we'll see a bit later.\n",
"- Addition **is** associative. 1 + (2 + 3) is the same as (1 + 2) + 3.\n",
"- String concatenation **is** associative. \"A\" + (\"B\" + \"C\") == (\"A\" + \"B\") + \"C\"\n",
" - Unlike numeric addition where 1 + 2 == 2 + 1, string concatenation is **not** _commutative_! Monoids only depend on the associative property. (See [Andrey Mokhov's article](https://blogs.ncl.ac.uk/andreymokhov/united-monoids/) for a fascinating deep-dive into this subject)\n",
"- Subtraction is **not** associative as order of composition matters. 1 - (2 - 3) is **not equal** to (1 - 2) - 3.\n",
"\n",
"\n",
"### Closed\n",
"\n",
"For a given operation, the input and output types must match for the operation to be closed.\n",
"- The minimum of two integers maps back into the set of integers.\n",
"\n",
"```python\n",
"def min_(a: int, b: int) -> int:\n",
" return min(a, b)\n",
"```\n",
"\n",
"- Multiplication of two integers stays within the set of integers.\n",
"\n",
"```python\n",
">>> type(42 * 7)\n",
"\n",
">>> a = 42\n",
">>> b = 7\n",
">>> type(a)\n",
"\n",
">>> type(b)\n",
"\n",
">>> type(a * b)\n",
"\n",
">>>\n",
"```\n",
"\n",
"- Floating point division of two integers returns a float, which is outside the set of integers. The _input_ and _output_ types don't match. This is **not** a closed operation.\n",
"\n",
"```python\n",
">>> type(42 / 33)\n",
"\n",
">>>\n",
"```\n",
"\n",
"- The `chr` function in Python takes an integer and returns a `str`. This operation is **not** closed for the same reason; the output is of a different type than the input.\n",
"\n",
"```python\n",
">>> type(chr(51))\n",
"\n",
">>>\n",
"```\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Axioms\n",
"\n",
"We're almost there! We need to mention identity. The importance of identity is a bit of a rabbit hole, so I'll leave it as an exercise for the reader to dig deeper (abstract algebra rings and rngs).\n",
"\n",
"An identity element is an element that does not change the output when paired with any other input.\n",
"\n",
"### Identity\n",
"\n",
"- Numeric addition: 0 is the identity (works with reals, integers, naturals, etc).\n",
"\n",
"```python\n",
">>> 42 + 0\n",
"42\n",
">>>\n",
"```\n",
"\n",
"- Numeric multiplication: 1 is the identity (gotcha! The identity is dependent on the _operation_ and the _type_).\n",
"\n",
"```python\n",
">>> 42 * 1\n",
"42\n",
">>>\n",
"```\n",
"\n",
"- List concatenation: the empty list is the identity\n",
"\n",
"```python\n",
">>> [1, 4, 3] + []\n",
"[1, 4, 3]\n",
">>>\n",
"```\n",
"\n",
"The reason we need this is a little subtle.\n",
"We are using a binary operation to make a computation, but what do we do when we only have one value to work with?\n",
"Many of the use cases of monoids are recursive in nature, so what do you do when you reduce a list to one element?\n",
"This is fairly representative of the problem (or imagine if `functools.reduce` didn't take a default argument).\n",
"\n",
"```python\n",
">>> list(map(lambda x, y: x + y, [42]))\n",
"Traceback (most recent call last):\n",
" File \"\", line 1, in \n",
"TypeError: () missing 1 required positional argument: 'y'\n",
">>>\n",
"```\n",
"\n",
"We can use the identity!\n",
"This allows the developer to safely perform a binary operation on a single element without changing the output.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Definition\n",
"\n",
"Hopefully, we now have the tools to unpack this definition...\n",
"\n",
"According to Eric Weisstein on Wolfram, a monoid is \"a set that is closed under an associative binary operation and has an identity element $I \\in S$ such that $ \\forall a \\in S, Ia=aI=a$\".\n",
"\n",
"I don't like that definition.\n",
"What the heck does $Ia=aI=a$ mean?\n",
"It _looks_ like multiplication, but that is one of many possible binary operations.\n",
"Here's my rephrasing: \n",
"A monoid consists of a set, $S$, that is closed under an associative binary operation, $f$, and has an identity element $I \\in S$ such that $ \\forall a \\in S, f(I, a)=f(a, I)=a$.\n",
"\n",
"A monoid has three components.\n",
"- The set $S$, often called the \"carrier set\". Programmers know this as a type (int, float, double, etc).\n",
"- $I$ is the identity element, which we identified in the previous section\n",
"- A binary operation. Addition, multiplication, list concatenation, etc.\n",
"\n",
"I said in the intro that you already know what a monoid is.\n",
"Here are some examples:\n",
"- Integers, addition, 0\n",
"- Reals, multiplication, 1\n",
"- Lists, concatenation, \\[ \\]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Why it matters\n",
"\n",
"At this point, you might be thinking about whipping me with a large stick for describing simple arithmetic in such obtuse and abstract terms.\n",
"It matters, I promise!\n",
"These definitions allow us to precisely identify objects with certain properties that support certain operations.\n",
"Enough math, why does this matter to programmers?!\n",
"\n",
"### Divide\n",
"\n",
"Remember how I said that associative property would be important later on?\n",
"Consider the following items... they're all equivalent.\n",
"\n",
" 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10\n",
" (1 + 2) + (3 + 4 + 5 + 6 + 7 + 8 + 9 + 10)\n",
" (1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + 10)))))))))\n",
" (((((((((1 + 2) + 3) + 4) + 5) + 6) + 7) + 8) + 9) + 10)\n",
"\n",
"Here's another example.\n",
"\n",
" \"a\" + \"b\" + \"c\" + \"d\" + \"e\" + \"f\" + \"g\" + \"h\" + \"i\" + \"j\"\n",
" \"ab\" + \"cd\" + \"ef\" + \"gh\" + \"ij\"\n",
" \"abcd\" + \"efgh\" + \"ij\"\n",
" \"abcdefgh\" + \"ij\"\n",
" \"abcdefghij\"\n",
"\n",
"I can write those down on a set of index cards and pass the pairs to two people at a time (think two CPU cores).\n",
"As long as I track the order of the results, I can recursively continue this process in any order of composition until the task is done.\n",
"This process succeeds even if the workers have different computational capacities.\n",
"The answer is the same as if one poor individual toiled away at the tasks independently.\n",
"\n",
"### More cores, more computers\n",
"\n",
"If the list is really long or the binary operation is non-trivial, we can **safely** and easily divide this tasks amongst different cores - or even different computers.\n",
"Notice that we are talking about _CPU_-bound tasks, not _IO_-bound tasks (multiple cores do little to alleviate the latter).\n",
"Python doesn't have the ability to do this natively, but other languages do.\n",
"\n",
"#### But be careful\n",
"\n",
"```python\n",
"from multiprocessing import Pool, cpu_count\n",
"import timeit\n",
"\n",
"\n",
"def read_data(fname: str):\n",
" \"\"\"Read Wiki tables\"\"\"\n",
" with open(fname) as fp:\n",
" items = fp.readlines()\n",
" return map(lambda item: int(item.split(\" \")[3]), items)\n",
"\n",
"\n",
"def do_it(fname):\n",
" \"\"\"Read data and perform calculation\"\"\"\n",
" data = read_data(fname)\n",
" return sum(data)\n",
"\n",
"\n",
"def multi_proc_demo() -> None:\n",
" N_PROC = cpu_count()\n",
" # Start the processes\n",
" with Pool(processes=N_PROC) as p:\n",
" results = []\n",
" fnames = [\n",
" \"data/pagecounts-20090601-000000\",\n",
" \"data/pagecounts-20090601-010000\",\n",
" \"data/pagecounts-20090601-020000\"\n",
" ]\n",
" for fname in fnames:\n",
" results.append(p.apply_async(do_it, kwds={'fname': fname}))\n",
" sum([result.get(timeout=5) for result in results])\n",
"\n",
"\n",
"def single_proc_demo() -> None:\n",
" # cat data/pagecounts* >> all.txt\n",
" sum(read_data(\"data/all.txt\"))\n",
"\n",
"\n",
"if __name__ == \"__main__\":\n",
" print(\"Multi-proc: \", timeit.Timer(\"multi_proc_demo()\", globals=globals()).repeat(5, 10))\n",
" print(\"Single-proc: \", timeit.Timer(\"single_proc_demo()\", globals=globals()).repeat(5, 10))\n",
"```\n",
"\n",
"```shell\n",
"python wiki.py\n",
"Multi-proc: [28.17182195998612, 28.688616012994316, 28.539513622003142, 28.077732990990626, 28.294970447997912]\n",
"Single-proc: [75.17859069499536, 73.89702447700256, 74.0759316909971, 74.918352623994, 74.7120841670112]\n",
"```\n",
"\n",
"The example above uses a publicly-available dataset from Wikipedia (linked in the References).\n",
"I spent way too much time fighting `multiprocessing`, but I learned a lot along the way.\n",
"Always RTFM!\n",
"There are several caveats to the library, and it is essential to read the [Programming Guidelines](https://docs.python.org/3/library/multiprocessing.html#programming-guidelines).\n",
"One of the issues is how Python copies memory to child processes.\n",
"This serialization overhead is huge, so it is much better for your child processes to retrieve their own data.\n",
"When in doubt, measure (the `timeit` library is great for this)!\n",
"What does this have to do with monoids?\n",
"\n",
"Since addition is a moniod, we can safely split the work up and aggregate the results.\n",
"It is also commutative which means that we don't even have to track the order of the results.\n",
"Not all operations are commutative, though!\n",
"If you are multiplying a bunch of matrices, you can still batch the computation, but you *must* track the order of the results.\n",
"\n",
"#### The right tool for the right job\n",
"\n",
"Know your use case.\n",
"I am an avid Pythonista, but sometimes alternatives might be the better choice.\n",
"Gloang doesn't read `all.txt` any faster, but it performs the summation in milliseconds instead of seconds!\n",
"Julia as native support for [multi-core processing](https://docs.julialang.org/en/v1/manual/parallel-computing/), and there are other languages that do as well.\n",
"\n",
"### And conquer\n",
"\n",
"This divide-and-conquer concept is critical to well-known large-scale algorithms like [MapReduce](https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html).\n",
"\n",
"It doesn't mean we can't do it ourselves, though!\n",
"Libraries like `multiprocessing` allow Python developers to delegate tasks among different cores or processors.\n",
"Keep in mind that just like delegating tasks to friends, there is a computational overhead to splitting up tasks.\n",
"It is important to understand that libraries like [`Numpy`](https://numpy.org/) don't [get you around the single-core limit](https://scipy.github.io/old-wiki/pages/ParallelProgramming) even though it is implemented in C.\n",
"Do your research!\n",
"Know your data and the problem domain before you start concatenating small strings across processes! ðŸ˜œ"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### BLS data\n",
"\n",
"Let's look at some data freely available from the Bureau of Labor Statistics.\n",
"I downloaded the flat files from the link in the references and created some `dataclasses` to support our operations.\n",
"This is a quick-and-dirty module.\n",
"I'm not doing any type checking or validation in an effort to minimize boilerplate and get to the essence of the post."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from functools import partial, reduce\n",
"from dataclasses import dataclass, asdict\n",
"\n",
"@dataclass(frozen=True)\n",
"class BLSRecord:\n",
" \"\"\"BLS table entry\"\"\"\n",
" series_id: str\n",
" year: str\n",
" period: str\n",
" value: str\n",
" footnote_codes: str\n",
"\n",
"@dataclass(frozen=True)\n",
"class BLSSeries:\n",
" \"\"\"BLS series entry\"\"\"\n",
" series_id: str\n",
" area_code: str\n",
" item_code: str\n",
" series_title: str\n",
" footnote_codes: str\n",
" begin_year: str\n",
" begin_period: str\n",
" end_year: str\n",
" end_period: str\n",
"\n",
"\n",
"def read_with_header(fname: str, rec_type):\n",
" \"\"\"Read BLS tables with header row\"\"\"\n",
" with open(fname) as fp:\n",
" items = fp.readlines()\n",
" # Skip the header row, split, strip, and instantiate the dataclass\n",
" return map(lambda item: rec_type(*map(str.strip, item.split(\"\\t\"))), items[1::])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Composition\n",
"\n",
"When dealing with business logic, we are often faced with brittle code when requirements change and that massive `if`/`else` block just keeps growing.\n",
"Even worse is when you realize that similar logic is needed in multiple parts of the code and it's unclear how to \"glue\" the pieces together.\n",
"\n",
"Here is a much less trivial example.\n",
"One of the key axioms is that we are dealing with **binary operations** that map some type to the same type.\n",
"Does this type have to be a number or a string?\n",
"Not at all!\n",
"Let's reconsider `sum` on integers; it takes two integers and returns an integer.\n",
"Replace integer with \"numeric type\", and we can still play ball.\n",
"Can we go further?\n",
"Here is the formula for standard deviation:\n",
"\n",
"$$ \\sigma = \\sqrt{\\frac{\\sum_{i=1}^N (x_i - \\bar{x})^2}{N-1}} $$\n",
"\n",
"Look at the summation $\\sum_{i=1}^N (x_i - \\bar{x})^2$ and break it down a little.\n",
"Couldn't we also say $\\sum_{i=1}^N func()$?\n",
"In other words, instead of passing some numeric type to `add`, I want to pass a _function_ that **returns** a numeric type to `add`.\n",
"This is a perfectly valid construction!\n",
"The cool thing is that we can *compose* functions that return numeric types with the `add` binary operation.\n",
"\n",
"We can use this idea with boolean operations to compose data queries instead of using an endless string of `if X and Y and Z` where `X`, `Y`, and `Z` tend to get lengthy in my experience."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"All records: 177,894\n",
"Coffee: 786\n",
"January: 15,042\n",
"Coffee and January: 66\n",
"Coffee and January and not 1995: 62\n"
]
}
],
"source": [
"\n",
"def is_coffee_lookup(rec: BLSRecord, lookup) -> bool:\n",
" return series_data[rec.series_id].item_code == \"717311\"\n",
"\n",
"def is_january(rec: BLSRecord) -> bool:\n",
" return rec.period == \"M01\"\n",
"\n",
"def is_not_1995(rec: BLSRecord) -> bool:\n",
" return rec.year != \"1995\"\n",
"\n",
"def intersect_identity(rec: BLSRecord) -> bool:\n",
" # The \"natural element\" for intersections is True\n",
" return True\n",
"\n",
"def intersect(fst_fn, snd_fn):\n",
" return lambda rec: fst_fn(rec) and snd_fn(rec)\n",
"\n",
"# Create a lookup table for series entries\n",
"series_data = {row.series_id: row for row in read_with_header(\"data/ap.series\", BLSSeries)}\n",
"\n",
"# Inject our state\n",
"is_coffee = partial(is_coffee_lookup, lookup=series_data)\n",
"\n",
"print(f\"All records: {len(price_data):,}\")\n",
"# Filter for entries that are coffee\n",
"print(f\"Coffee: {len(list(filter(is_coffee, price_data))):,}\")\n",
"# Filter for entries that are in January\n",
"print(f\"January: {len(list(filter(is_january, price_data))):,}\")\n",
"\n",
"# Compose and profit!\n",
"coffee_and_january = reduce(intersect, [is_coffee, is_january], intersect_identity)\n",
"print(f\"Coffee and January: {len(list(filter(coffee_and_january, price_data))):,}\")\n",
"\n",
"# We can compose any number of functions that are valid Moniods!\n",
"coffee_and_january_not_1995 = reduce(intersect, [is_not_1995, is_coffee, is_january], intersect_identity)\n",
"print(f\"Coffee and January and not 1995: {len(list(filter(coffee_and_january_not_1995, price_data))):,}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Conclusion\n",
"\n",
"I hope I didn't chase too many rabbits; there are plenty to chase on this topic!\n",
"I also hope that this has sparked some ideas and will help you identify common patterns in software that will make your coding a bit more efficient and clean.\n",
"\n",
"## References\n",
"\n",
"- Weisstein, Eric W. \"Monoid.\" From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Monoid.html \n",
"- https://en.wikipedia.org/wiki/Monoid\n",
"- https://wiki.haskell.org/Monoid\n",
"- https://github.com/dry-python/functional-jargon-python\n",
"- https://planetmath.org/examplesofnoncommutativeoperations\n",
"- https://blogs.ncl.ac.uk/andreymokhov/united-monoids/\n",
"\n",
"## Data\n",
"\n",
"- https://download.bls.gov/pub/time.series/ap\n",
"- https://archive.org/details/wikipedia_visitor_stats_200906"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.7.9"
},
"nikola": {
"category": "",
"date": "2020-10-05 07:30:10 UTC-05:00",
"description": "",
"link": "",
"slug": "monoids-for-pythonistas",
"tags": "math,python,category-theory",
"title": "Monoids for Pythonistas",
"type": "text"
}
},
"nbformat": 4,
"nbformat_minor": 2
}