{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"focus": false,
"id": "1100a234-c53d-4407-a4d3-fccb1ef66b07",
"outputExpanded": false
},
"source": [
"# Introducing Functor\n",
"\n",
"\n",
"In programing, you often embed some domain specific language in a host language. This might be for working with databases, or working with configuration. And when you have such DSL, you will probably want to use functions from your host-language on values from your dsl. Some database libraries are quite bad in this regard, where you set your queries as literal strings:\n",
"\n",
"```\n",
"session.execute(\"select text,priority from memos where priority>9;\")\n",
"```\n",
"\n",
"On the other hand, if you use library, such as sql-alchemy, the interoperabilty with the host-language is much more seamless:\n",
"\n",
"```\n",
"session.query(Memos).filter(Memos.priority > 9)\n",
"```\n",
"\n",
"When you look at the code, it is apparent that some translation needs to happen that would convert the python expression `Memos.priority > 9` to the SQL equivalent.\n",
"\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {
"outputExpanded": false
},
"source": [
"# Category theory!\n",
"\n",
"This idea of translating objects from one domain to another is at the core of the mathematical subject of category theory. \n",
"\n",
"Category in mathemathics is defined by three things:\n",
"* collection of objects\n",
"* collection of possible transformations between these objects, called morphisms\n",
"* if we can transform object X to Y, and we can transform object Y to Z, there needs to be transformation from A to C in our transformation collection\n",
"\n",
"You could draw a category using upper-case letters for objects, and arrows to signify possible transformations.\n",
"\n",
"![Category](https://upload.wikimedia.org/wikipedia/commons/e/ef/Commutative_diagram_for_morphism.svg)\n",
"\n",
"Functor is then mapping between categories. On the image you can see a category of red objects, with morphisms $f$, $g$ and three identity morphisms (i.e. arrows that transform and object to itself) and a functor $F$ that *lifts* the transformations from red category, to green, where there are only two objects.\n",
"\n",
"![Functor](https://upload.wikimedia.org/wikibooks/en/3/36/Functor.png) \n",
"\n",
"I am not entirely sure I could say, that you could think of i.e. predicates in python as one category, predicates in sql as other category, and that sql-alchemy would form a functor between them. But even if that wouldn't be entirely true, it gives nice intuition for what we would want to achieve with utilizing category-theory in programming."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Functor in Python\n",
"\n",
"So what in practice is a functor?\n",
"\n",
"In general, anything where you can define a sensible `fmap(function, )` operation. The anything in question are mostly containers, but it might be a generic object providing aditional context/metadata, for value(s) it could encapsulate, or produce. \n",
"\n",
"\n",
"*Sensible* in this context means, that the interface obeys certain laws, but before we state them expricitly, I need to define two functions, `id` and `compose`:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def id(x):\n",
" return x\n",
"\n",
"def compose(f,g):\n",
" return lambda x: f(g(x))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The idea goes like this:\n",
"* we have our generic type T, parametrized by type A, or T[A] in [typings syntax](https://docs.python.org/3/library/typing.html)\n",
"* we interpret T[A], that our T can in some way produce value(s) of type A\n",
"\n",
"T is a **functor**, if\n",
" * if we can easily convert T[A] (a producer of A's) to T[B] (a producer of A's), by using the function `fmap(fn, t)`, if we have function that accepts A and returns B\n",
" * identity function doesn't indroduce changes: \n",
" * `fmap(id, t) == t`\n",
" * if we have functions f and g that are composable, it doesn't matter if we compose them first, or use fmap twice: \n",
" * `fmap(compose(f,g),t) == fmap(f,fmap(g,t))`\n",
"\n",
"The `fmap(id, t) == t` and `fmap(compose(f,g),t) == fmap(f,fmap(g,t))` are the functor laws. I try to explain why should we care about them later, I'd rather show few concrete examples now: "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['1', '2', '3']"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def fmapList(fn, lst):\n",
" return [fn(x) for x in lst]\n",
"\n",
"fmapList(str,[1,2,3])"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def fmapIterable(fn, iterable):\n",
" return (fn(x) for x in iterable)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class Tree:\n",
" def __init__(self,left=None,data=None,right=None):\n",
" self.left = left\n",
" self.right = right\n",
" self.data = data \n",
" \n",
"def fmapTree(fn, tree):\n",
" if tree == None:\n",
" return None\n",
" else:\n",
" return Tree(\n",
" mapTree(fn,tree.left),\n",
" fn(tree.data),\n",
" mapTree(fn,tree.right)\n",
" )"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Interestingly enough, there is a `map` function in Python, and it works on iterables. Which unfortunately means that it allways returns an iterable. The interesting thing about functors is, that the map function preserves the type. If I map over list, I know it will be a list.\n",
"\n",
"But there are more interesting things than containers that could be functors, for example functions:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def fmapFunction(function, fn):\n",
" def wrapper(*arr):\n",
" return fn(function(*arr))\n",
" return wrapper"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we can convert function that generates random integers to function that generates strings."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'6'"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"fmapFunction(random.randint, str)(1,10)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Lift for our functions\n",
"\n",
"There is a recuring concept, where we use some bit of information about\n",
"our datatype to convert functions that know nothig about it, to work with it.\n",
"\n",
"We call this *lifting*.\n",
"\n",
"For example, because I know that lists have map function, I could lift i.e. `str` to work on lists of things.\n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": true,
"focus": true,
"id": "1ecdf7b5-e436-46ee-914a-f8cd3646b1a0",
"outputExpanded": false
},
"outputs": [],
"source": [
"def lift(fn):\n",
" def liftedfn(x):\n",
" return fmapList(fn,x)\n",
" return liftedfn "
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"focus": false,
"id": "dec0bd55-0da9-4da3-b359-75269144686c",
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"['1', '2', '3']"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lifted_str = lift(str)\n",
"lifted_str([1,2,3])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Making this more usable\n",
"\n",
"Interesting question is, how to make these more pleasan't to use. One approach might be defining fmap as @singledispatch, as we did with mconcat previously. Only thing that is a bit awkward is, that we can't have the function argument first."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from functools import singledispatch, partial\n",
"\n",
"@singledispatch\n",
"def fmap(x, fn):\n",
" raise Error(\"Not implemented for\" + a)\n",
" \n",
"def lift(fn):\n",
" def liftedfn(x):\n",
" return fmap(x, fn)\n",
" return liftedfn "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we could register a few classes that would work with this.\n",
"I.e. all of the collections such as list:"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"@fmap.register([].__class__)\n",
"def _(lst, fn):\n",
" return [fn(x) for x in lst]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"set:"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"@fmap.register(set().__class__)\n",
"def _(lst, fn):\n",
" return set(fn(x) for x in lst)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"dictionary:"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"@fmap.register({}.__class__)\n",
"def _(d, fn):\n",
" return {x: fn(d[x]) for x in d}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Why should we care about lawfulness?\n",
"\n",
"For functor, I have some intuition for its laws, because I had abstract algebra course at university and when I look at the laws my mins goes \"This kida looks like definition of homomorphism, I remember those to be useful, I guess it makes sense then.\" I dont really remember the specifics, but because it is vaguely familliar, I am fine with it.\n",
"\n",
"There is better reason to like lawful interfaces, though. Just by using the the laws of the interface, we can define new and usefull stuff.\n",
"\n",
"Lets look at nesting of two different functors, where we would have T[U[A]]. It is easy to see, that for any a, T[U[a]] is a functor as well.\n",
"\n",
"If map for T is tmap, and map for U is umap, we can define the tumap for the nesting of U in T like this:\n",
"\n",
"```\n",
"def tumap(f,tu):\n",
" return tmap(lambda x: umap(f,x), tu)\n",
"```\n",
"\n",
"We could write this as:\n",
"\n",
"$$ \\begin{align*} \\text{map}_{t_u}(f, t_u) &= {map}_{t} ( \\lambda x: map_u(f,x), t_u) \\end{align*} $$\n",
"\n",
"And because we know the functor laws we can try to prove that they hold for this implementation as well.\n",
"\n",
"* for any `tu`, `tumap(id, tu) == tu`\n",
"\n",
"$$ \\begin{align*} \\text{map}_{t_u}(id, t_u) &= {map}_{t} ( \\lambda x: map_u(id,x), t_u) \\\\\n",
"&= {map}_{t} ( \\lambda x: x, t_u) \\\\\n",
"&= {map}_{t} ( id, t_u) \\\\\n",
"&= t_u \\\\\n",
"\\end{align*} $$\n",
"\n",
"* for any t and any two composable functions f and g, tumap(f,tumap(g,tu)) == map(compose(f,g),tu)\n",
"\n",
"$$ \\begin{align*} \\text{map}_{t_u}(f, {map}_{tu}(g,t_u)) &= \\text{map}_{t_u}(f, {map}_{tu}(g,t_u)) \\\\\n",
"&= {map}_{t} ( \\lambda x: map_u(f,x), {map}_{t}( \\lambda x: map_u(g,x),t_u)) \\\\\n",
"&= {map}_{t}((\\lambda x: map_u(f,x)) \\circ (\\lambda x: map_u(g,x)), t_u) \\\\ \n",
"&= {map}_{t}(\\lambda x: map_u(f,map_u(g,x)), t_u) \\\\\n",
"&= {map}_{t} ( \\lambda x: map_u(compose(f,g),x), t_u) \\\\\n",
"&= \\text{map}_{t_u}(compose(f,g), t_u) \n",
"\\end{align*} $$\n",
"\n",
"Because we have laws for the interface, we can do these kinds of self-contained proofs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Now we can do nested fmap\n",
"\n",
"Because we know, that functor of a functor is a functor, we can attempt a nested fmap. "
]
},
{
"cell_type": "code",
"execution_count": 101,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def fmapNested(xs, fn):\n",
" def recur(x):\n",
" if x.__class__ in fmap.registry.keys():\n",
" return fmap(x,recur)\n",
" else:\n",
" return fn(x)\n",
" return fmap(xs,recur)\n",
"\n",
"def liftNested(fn):\n",
" return lambda x: fmapNested(x,fn)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Yay, now we can map over nested data-structures!"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['1', '2'], {'a': ['3', '4']}]"
]
},
"execution_count": 86,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fmapNested([[1,2],{'a':[3,4]}],str)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Effect tracking\n",
"\n",
"Now, the interesting thing you can use functors for, is to track various side-effects and their meta-data with them. This is what i.e. Haskell does. The fmap then gives you the ability to say \"I don't care about anything, just let me operate on the inner value(s)\". These values might not be there, there might be error instead, there might be many, you might need to wait for a http request to complete, but with fmap, you can choose to ignore it, and just fmap over the values."
]
},
{
"cell_type": "code",
"execution_count": 88,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class ErrorOrValue:\n",
" def __init__(self,error,value):\n",
" self._error = error\n",
" self._value = value\n",
" \n",
" def map(self,fn):\n",
" if self._error:\n",
" return self\n",
" else:\n",
" return ErrorOrValue(None,fn(self._value))\n",
" \n",
" def __repr__(self):\n",
" if self._error:\n",
" return \"Error:\" + self._error\n",
" else:\n",
" return \"Value:\" + repr(self._value)\n",
" \n",
"@fmap.register(ErrorOrValue)\n",
"def _(x,fn):\n",
" return x.map(fn)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With this, I can implement a silly little square-root function:\n",
"* that would return the both results of square root :-)\n",
"* that returns an error if there is no result"
]
},
{
"cell_type": "code",
"execution_count": 100,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Value:[4.0, -4.0]\n",
"Error:Can't sqrt -16\n"
]
}
],
"source": [
"import math\n",
"def sqrt(x):\n",
" if x>=0:\n",
" return ErrorOrValue(None,[math.sqrt(x), - math.sqrt(x)])\n",
" else:\n",
" return ErrorOrValue(\"Can't sqrt \"+str(x),None)\n",
"\n",
"print(sqrt(16))\n",
"print(sqrt(-16))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On one hand, suddenly I can't just do `sqrt(sqrt(sqrt(256)))`"
]
},
{
"cell_type": "code",
"execution_count": 105,
"metadata": {},
"outputs": [
{
"ename": "TypeError",
"evalue": "unorderable types: ErrorOrValue() >= int()",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0msqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m256\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36msqrt\u001b[0;34m(x)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0msqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m>=\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mErrorOrValue\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: unorderable types: ErrorOrValue() >= int()"
]
}
],
"source": [
"sqrt(sqrt(sqrt(256)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"But I have my nested lift function, that can fix this:"
]
},
{
"cell_type": "code",
"execution_count": 109,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Value:[Value:[Value:[2.0, -2.0], Error:Can't sqrt -4.0], Error:Can't sqrt -16.0]]"
]
},
"execution_count": 109,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lsqrt = liftNested(sqrt)\n",
"lsqrt(lsqrt(lsqrt([256])))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In practice, you wouldn't probably use this sort of nesting. But it hints on interesting building blocks that are useful. And for the most part, this is what functors are. A basic building block, that more interesting things are based upon. For example, right now, we can only lift single-param functions. We should be able to solve this somehow."
]
}
],
"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.5.1"
},
"nikola": {
"category": "",
"date": "2017-05-11 17:25:35 UTC+02:00",
"description": "",
"link": "",
"slug": "functor-pattern-in-python",
"tags": "algebraic-patterns",
"title": "Functor pattern in Python",
"type": "text"
}
},
"nbformat": 4,
"nbformat_minor": 2
}