{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "FP idioms in Python\n", "===================\n", "\n", "_A whirlwind tour of the available, the usable, and the undesirable._\n", "\n", "\n", "Preliminaries\n", "-------------\n", "\n", "_\"Monads are just monoids in the category of endofunctors.\"_\n", "\n", "Main intent: demystify FP style without jargon and demo some nice techniques. We'll call \"FP\" the kinds of techniques you use when functions are ordinary types and lists (arrays) are baked in.\n", "\n", "Our motivation for using FP style:\n", "\n", "* brain expansion: this stuff is fun. There are other ways to code!\n", "* making it easy to reason about things\n", "* making things easily testable\n", "* removing sources of bugs by removing variables and state\n", "* translating algorithms from FP languages\n", "\n", "We will also point out where you can have too much of this good thing.\n", "\n", "Remember in what follows that Guido is not our friend and Pythonistas are particular about the Pythonic.\n" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Baked in support" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Functions are first class types in Python. That's what makes everything that follows work. It's true of most modern languages these days, but those of us who learned to program in earlier times will have used many languages where you can't assign a function to variable or pass a function to another function.\n", "\n", "You can make anonymous one-statement functions with the *lambda* keyword." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# fn is a perfectly respectable function\n", "\n", "fn = lambda x,y: x*y\n", "\n", "type(fn)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 123, "text": [ "builtins.function" ] } ], "prompt_number": 123 }, { "cell_type": "code", "collapsed": false, "input": [ "fn(2,4)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 124, "text": [ "8" ] } ], "prompt_number": 124 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Otherwise, you can define named functions with *def* that return things with *return*.\n", "\n", "Note that Python functions defined with *def* are not necessarily functions in the FP sense. They don't have to return anything and they can have side-effects. In FP-speak, having side-effects makes a function _impure_. Ewwww. Impure functions are yukky. Also, by definition, a function has a result -- it maps a thing to another thing.\n", "\n", "Pure functions are easier to understand at a glance, don't cause debugging mysteries, and lend themselves to unit tests." ] }, { "cell_type": "code", "collapsed": true, "input": [ "def pure_fn(x,y):\n", " z = x + y\n", " return z * 2\n", "\n", "def impure_fn(l):\n", " print(l)\n", " l[0] = l[0] -1\n", " # and we don't even return anything, how rude\n", "\n", "mylist = [2]\n", "impure_fn(mylist)\n", "print(mylist)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "[2]\n", "[1]\n" ] } ], "prompt_number": 125 }, { "cell_type": "code", "collapsed": true, "input": [ "# Functions are values and so... \n", "a = pure_fn\n", "\n", "a(5,6)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 126, "text": [ "22" ] } ], "prompt_number": 126 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Functions defined with _lambda_ and functions defined with _def_ are both just plain Python functions. They just happen to have been defined with different syntax.\n", "\n", "There are builtins for some common functional idioms, in the form of *map* and *filter*. These both return \"iterables\", not lists, which can be a bit annoying. Earlier Pythons returned lists." ] }, { "cell_type": "code", "collapsed": false, "input": [ "l = [5,3,5,6,1,2,9,3]\n", "\n", "double_l = map(lambda x: x * 2, l)\n", "\n", "double_l" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 127, "text": [ "" ] } ], "prompt_number": 127 }, { "cell_type": "code", "collapsed": false, "input": [ "# We have to cast result to\n", "# list type with list()\n", "\n", "list(double_l)\n", "l" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 128, "text": [ "[5, 3, 5, 6, 1, 2, 9, 3]" ] } ], "prompt_number": 128 }, { "cell_type": "code", "collapsed": false, "input": [ "l = [5,3,5,6,1,2,9,3]\n", "\n", "list(filter(lambda x: x % 2 == 0, l))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 129, "text": [ "[6, 2]" ] } ], "prompt_number": 129 }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Fold and reduce" ] }, { "cell_type": "code", "collapsed": false, "input": [ "help(functools.reduce)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Help on built-in function reduce in module _functools:\n", "\n", "reduce(...)\n", " reduce(function, sequence[, initial]) -> value\n", " \n", " Apply a function of two arguments cumulatively to the items of a sequence,\n", " from left to right, so as to reduce the sequence to a single value.\n", " For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n", " ((((1+2)+3)+4)+5). If initial is present, it is placed before the items\n", " of the sequence in the calculation, and serves as a default when the\n", " sequence is empty.\n", "\n" ] } ], "prompt_number": 130 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Up until Python3, there was *reduce*, which you might know as \"fold\". Guido killed _reduce_ in Python 3, saying that list comprehensions had eliminated the need for it and it was always a wart. People who disagree can use the _reduce_ provided by the functools module.\n", "\n", "Here's a minimal version to show what it does and how. Don't use this implementation because it will blow up in various ways without extra code. The functools version is written in C, probably for speed and to avoid blowing up the stack. We'll talk about that later." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def reduce_(fn, seq, seed=None):\n", " \"\"\"\n", " fn is a function that takes two arguments and returns one result.\n", " \n", " The initial seed is optional.\n", " \n", " If there's one thing left in the sequence, use it as an arg and the seed as the other.\n", "\n", " Otherwise, recursively eat up the sequence.\n", " \"\"\"\n", " \n", " if len(seq) == 1 and seed is None:\n", " return seq[0]\n", " elif len(seq) == 0:\n", " return seed\n", " \n", " return fn(seq[0], reduce_(fn, seq[1:], seed))\n", "\n", "def tish(s1, s2):\n", " return s1 + \" TISH \" + s2\n", "\n", "# 2! 4! 6! 8! EVERYONE INTERCALATE!\n", "reduce_(tish, [\"BOOM\", \"BOOM\", \"BOOM\", \"BOOM\"])" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 131, "text": [ "'BOOM TISH BOOM TISH BOOM TISH BOOM'" ] } ], "prompt_number": 131 }, { "cell_type": "code", "collapsed": false, "input": [ "reduce_(lambda x, y: x+y, [1, 2, 3, 4, 5], 10)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 132, "text": [ "25" ] } ], "prompt_number": 132 }, { "cell_type": "markdown", "metadata": {}, "source": [ "List comprehensions. I like to think of a comprehension as a way to *do a thing* with some *items* if they *pass a test*. This isn't exactly common FP style, but, it has no sideeffects per se, and it's borrowed from Haskell, so it kind of smells like FP." ] }, { "cell_type": "code", "collapsed": false, "input": [ "fruits = [\"apple\", \"banana\", \"avocado\"]\n", "\n", "# cf Haskell\n", "# import Data.Char\n", "# [map toUpper fruit | fruit <- [\"apple\", \"banana\", \"pear\"], head fruit == 'a']\n", "\n", "[fruit.upper() for fruit in fruits if fruit.startswith(\"a\")]" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 133, "text": [ "['APPLE', 'AVOCADO']" ] } ], "prompt_number": 133 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Because functions are first class types, we can make functions that make functions." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def adder_factory(i):\n", " k = 30\n", " def adder(j):\n", " # i, j and k are \"open\" variables in adder's scope\n", " return i + j + k\n", " \n", " return adder\n", " \n", "add5 = adder_factory(5)\n", "\n", "adder_factory = None\n", "\n", "# Mysteriously, i j and k must still be around somehow. Those bindings were closed.\n", "add5(10)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 134, "text": [ "45" ] } ], "prompt_number": 134 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Did I mention Python has closures? A closure is what happens when a function keeps references to things that were in its environment when it was created, even if the original scope they were from has disappeared.\n", "\n", "Finally, there is some nice syntactic sugar for functions that make other functions, called decorators." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def print_args(fn):\n", " \"\"\"\n", " We're going to make a new function called \"wrapped\".\n", " \n", " wrapped will get called whenever another function is decorated with print_args.\n", " \n", " \"\"\"\n", " def wrapped(*args):\n", " print (\"Called\", fn.__name__, \"with:\", args,)\n", " result = fn(*args)\n", " print (\"resulting in:\", result)\n", " return result\n", " \n", " return wrapped\n", "\n", "@print_args\n", "def add_nums(i, j):\n", " return i + j\n", "\n", "add_nums(4,5)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Called add_nums with: (4, 5)\n", "resulting in: 9\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 135, "text": [ "9" ] } ], "prompt_number": 135 }, { "cell_type": "markdown", "metadata": {}, "source": [ "This \"@\" syntax is just a nice way of tidying up a function that makes another function. It's pretty much the same as this:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def add_nums2(i, j):\n", " return i + j\n", "\n", "add_nums2 = print_args(add_nums2)\n", "\n", "add_nums2(4,5)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Called add_nums2 with: (4, 5)\n", "resulting in: 9\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 136, "text": [ "9" ] } ], "prompt_number": 136 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that this is a naive decorator example -- in practice, you should do things like tidy up the name of the wrapped function to help with debugging. There are whole modules of helpers for this. Python people love using decorators but are often scared of writing them, for some reason.\n", "\n", "Also, there's no need to do logging like this, but it seems to be the classic example for this kind of thing.\n", "\n", "Anyway, if you've ever used decoraters, you were doing functional programming all along!" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Batteries included\n" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import itertools\n", "import functools\n", "import operator\n", "\n", "list(itertools.accumulate( [1,2,3,4], operator.add))\n", "#help(itertools.accumulate)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 137, "text": [ "[1, 3, 6, 10]" ] } ], "prompt_number": 137 }, { "cell_type": "markdown", "metadata": {}, "source": [ "_itertools_ mostly contains functions for working with lists -- the kind of thing you might find in the Haskell Prelude. Also includes __accumulate()__, which works like Haskell __scan__.\n", "\n", "_functools_ has helpers to set up partial application, write generic functions more easily, and make wrapped functions behave better. Also includes __reduce()__, which you may recognise as __fold__.\n", "\n", "_operator_ provides functions that are the equivalent of Python's builtin operators. Unlike say Haskell, Python operators are not functions with sugar, so you need something like this to work with them effectively in a functional style." ] }, { "cell_type": "code", "collapsed": false, "input": [ "import functools\n", "import operator\n", "\n", "functools.reduce(operator.mul, [1,2,3,4])" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 138, "text": [ "24" ] } ], "prompt_number": 138 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Traps for the unwary" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Python list class has methods that seem like the built-in functions sort and reverse. However, they do not return a transformed copy. They modify the list in place and return nothing. Every time I've been away from Python for a while, this trips me up." ] }, { "cell_type": "code", "collapsed": false, "input": [ "l = [3, 2, 5, 1]\n", "\n", "sorted(l)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 139, "text": [ "[1, 2, 3, 5]" ] } ], "prompt_number": 139 }, { "cell_type": "code", "collapsed": false, "input": [ "l" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 140, "text": [ "[3, 2, 5, 1]" ] } ], "prompt_number": 140 }, { "cell_type": "code", "collapsed": false, "input": [ "l.sort()\n", "l" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 141, "text": [ "[1, 2, 3, 5]" ] } ], "prompt_number": 141 }, { "cell_type": "code", "collapsed": false, "input": [ "l.sort()" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 142 }, { "cell_type": "code", "collapsed": false, "input": [ "print (list(reversed(l))) # reversed returns an iterator" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "[5, 3, 2, 1]\n" ] } ], "prompt_number": 143 }, { "cell_type": "code", "collapsed": false, "input": [ "print (l)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "[1, 2, 3, 5]\n" ] } ], "prompt_number": 144 }, { "cell_type": "code", "collapsed": false, "input": [ "l.reverse()\n", "print (l)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "[5, 3, 2, 1]\n" ] } ], "prompt_number": 145 }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "__map(function, iterable, ...)__\n", "\n", " Return an iterator that applies function to every item of iterable, yielding the results. If additional iterable arguments are passed, function must take that many arguments and is applied to the items from all iterables in parallel. With multiple iterables, the iterator stops when the shortest iterable is exhausted. For cases where the function inputs are already arranged into argument tuples, see itertools.starmap().\n", "\n", "I'm sorry, this is just weird. Or at least unlike the way most FP languages deal with _map_ and functions that take more than one argument." ] }, { "cell_type": "code", "collapsed": false, "input": [ "list(map((lambda tup:tup[0]*tup[1]), [(2,3),(4,4)]))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 146, "text": [ "[6, 16]" ] } ], "prompt_number": 146 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Late binding can be a pain." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# This example and subsequent para stolen from Brian Chikilian\n", "\n", "def create_multipliers():\n", " return [lambda x : i * x for i in range(5)]\n", "\n", "for multiplier in create_multipliers():\n", " print (multiplier(2))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "8\n", "8\n", "8\n", "8\n", "8\n" ] } ], "prompt_number": 147 }, { "cell_type": "markdown", "metadata": {}, "source": [ "This happens due to Python\u2019s late binding behavior which says that the values of variables used in closures are looked up at the time the inner function is called. So in the above code, whenever any of the returned functions are called, the value of i is looked up in the surrounding scope at the time it is called (and by then, the loop has completed, so i has already been assigned its final value of 4).\n", "\n", "The solution to this common Python problem is a bit of a hack." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def create_multipliers():\n", " return [lambda x, i=i : i * x for i in range(5)] # note the i=i in the lambda parameter\n", "\n", "for multiplier in create_multipliers():\n", " print (multiplier(2))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "0\n", "2\n", "4\n", "6\n", "8\n" ] } ], "prompt_number": 148 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Function composition: on the edge of Pythonic acceptability" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Composition is a very powerful technique for building up pipelines of transformations, expressing things concisely, and making sure nothing stomps on your intermediate variables.\n", "\n", "When you compose functions, they need to have compatible types. Python doesn't hold your hand a whole lot here, which is why this is best used sparingly." ] }, { "cell_type": "code", "collapsed": false, "input": [ "import functools\n", "\n", "def _compose_helper(fn1, fn2):\n", " # Make a new function that takes the args,\n", " # calls fn1 with them\n", " # and then passes the result to fn2\n", " def _fn(*args):\n", " return fn1(fn2(*args))\n", " \n", " return _fn\n", "\n", "def compose(*fns):\n", " # Glom all the functions in fns together\n", " # by repeatedly applying _compose_helper\n", " return functools.reduce(_compose_helper, fns)\n", "\n", "# Side note on readability: if we were steeped in FPness, we might just write:\n", "compose2 = lambda *fns: functools.reduce(lambda f1, f2: lambda *args: f1(f2(*args)), fns)\n", "\n", "# Resist that urge if you want to have friends.\n", " \n", "def centre_wide(s):\n", " return s.center(80)\n", "\n", "def upper(s):\n", " return s.upper()\n", "\n", "def word_count(s):\n", " return s + \"(%d)\" % len(s.split())\n", "\n", "def no_pants(s):\n", " return s.replace(\"trousers\", \"****\")\n", "\n", "lines = [\"In the beginning\",\n", " \"there was stuff like trousers\", \n", " \"but we hated wearing trousers because trousers suck\"]\n", "\n", "star_wars = compose2(upper, \n", " word_count,\n", " centre_wide, \n", " no_pants, \n", " )\n", "\n", "print(\"\\n\".join([star_wars(s) for s in lines]))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " IN THE BEGINNING (3)\n", " THERE WAS STUFF LIKE **** (5)\n", " BUT WE HATED WEARING **** BECAUSE **** SUCK (8)\n" ] } ], "prompt_number": 149 }, { "cell_type": "markdown", "metadata": {}, "source": [ "

From a talk I'm working on: compose2 = lambda *fns: functools.reduce(lambda f1, f2: lambda *args: f1(f2(*args)), fns) So ashamed.

— Mr Salteena (@saniac) June 29, 2015
\n", "\n", "\n", "

@saniac The fuck.

— Rob Isaac (@rmi) June 29, 2015
\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Things you might like to do but probably shouldn't\n", "--------------------------------------------------\n", "\n", "- use recursive algorithms from your FP textbooks without careful thought. (Why? No tail call optimisation in standard interpreter).\n", "- roll your own compose. (Why? No help from the type system, and it's really unidiomatic).\n", "- nest lambdas or even use them except as arguments to other functions. (Again, not Pythonic).\n", "- use reduce in complex ways. (Sigh, not Pythonic -- explicit loops are regarded as a good thing).\n", "- pile up too many function calls without intermediate variables. (Why? Because tracebacks aren't helpful.)\n", "\n", "However, if you want your co-workers to hate you, you can do what one guy did, and abuse Python's ability to override operators to allow the creation of code in point free style:\n", "\n", "Pipe is a Python module enabling infix syntax in Python.\n", "For those asking \u201cWhy ?\u201d let\u2019s take an example :\n", "\n", "Compare the readability of the classical prefix syntax :\n", "\n", " sum(select(where(take_while(fib(), lambda x: x < 1000000) lambda x: x % 2), lambda x: x * x))\n", "\n", "And the infix syntax :\n", "\n", " fib() | take_while(lambda x: x < 1000000) \\\n", " | where(lambda x: x % 2) \\\n", " | select(lambda x: x * x) \\\n", " | sum()\n", "\n", "Isn\u2019t the infix syntax more readable ?\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "References:\n", "\n", "- https://docs.python.org/3.4/howto/functional.html\n", "- http://www.artima.com/weblogs/viewpost.jsp?thread=98196\n", "- http://www.toptal.com/python/top-10-mistakes-that-python-programmers-make\n", "- http://dev-tricks.net/pipe-infix-syntax-for-python" ] } ], "metadata": {} } ] }