# Functional Programming with Python

### by Alexey Kachayev, 2012

• Position: CTO at Kitapps Inc.
• Production experience: Python, Java, JS, Go, Scala, Clojure, Erlang
• Looked at: Haskell, Lisp, Scheme

## Goals

• Dispel popular myths about FP
• Characterize Python & FP relations
• Why should I care? How can I make my code better?

### More How, less Why

• Imperative programming (С/C++, Java)
• Declarative programming
• Functional programming (Haskell, Scheme, OCaml)
• Logic programming (Prolog, Clojure core.logic)

• IP = computation in terms of statements that change a program state
• FP = computation as the evaluation of mathematical functions and avoids state and mutable data

• Avoid state
• Immutable data
• First-class functions
• Higher-order functions
• Pure functions
• Recursion, tail recursion
• Iterators, sequences, lazy evaluation, pattern matching, monads....

### "Imperative terminal"

``````\$ ./program1
\$ ./program2 --param1=1
\$ ./program3``````

### "Functional terminal"

``\$ ./program1 | ./program2 --param1=1 | ./program3``

Calculate partially invalid string with operations: "28+32+++32++39"

Imperative style = actions that change state from initial state to result

``````expr, res = "28+32+++32++39", 0
for t in expr.split("+"):
if t != "":
res += int(t)

print res``````
``````"28+32+++32++39", 0
"28", 0
"32", 28
"", 60
"", 60
"32", 60
"", 92
"39", 92
131``````

Functional style = apply transformation (and compositions)

``````from operator import add
expr = "28+32+++32++39"

``````"28+32+++32++39"
["28","32","","","32","","39"]
["28","32","32","39"]
[28,32,32,39]
131``````

## map/reduce/filter

• Technical aspects VS. operation substance
• Code reusage ("pluggability")

## Python hints

### Module "operator"

``````>>> operator.add(1,2)
3
>>> operator.mul(3,10)
30
>>> operator.pow(2,3)
8
>>> operator.itemgetter(1)([1,2,3])
2``````

## Python hints

### Module "itertools"

``````>>> list(itertools.chain([1,2,3], [10,20,30]))
[1, 2, 3, 10, 20, 30]
>>> list(itertools.chain(*(map(xrange, range(5)))))
[0, 0, 1, 0, 1, 2, 0, 1, 2, 3]
>>> list(itertools.starmap(lambda k,v: "%s => %s" % (k,v),
...                        {"a": 1, "b": 2}.items()))
['a => 1', 'b => 2']
>>> list(itertools.imap(pow, (2,3,10), (5,2,3)))
[32, 9, 1000]
>>> dict(itertools.izip("ABCD", [1,2,3,4]))
{'A': 1, 'C': 3, 'B': 2, 'D': 4}``````

## Can we avoid loops?

``````>>> name = None
>>> while name is None:
...    name = raw_input()
...    if len(name) < 2:
...        name = None``````

### Recursion

``````def get_name():
name = raw_input()
return name if len(name) >= 2 else get_name()``````

## Tail recursion?

### Erlang

``````fib(N) -> fib(0,1,N).
fib(_,S,1) -> S;
fib(F,S,N) -> fib(S,F+S,N-1).``````

sorry...

## Functions

### First-class

``````def add(a, b):
return a + b``````

``add = lambda a,b: a + b``

``````def calculations(a, b):
return a + b

### High-ordered function

Pass function as argument

``map(lambda x: x^2, [1,2,3,4,5])``

### High-ordered function

Function returns function as result

``````def speak(topic):
print "My speach is " + topic

def timer(fn):
def inner(*args, **kwargs):
t = time()
fn(*args, **kwargs)
print "took {time}".format(time=time()-t)

return inner

speaker = timer(speak)
speaker("FP with Python")``````

### High-ordered function

``````@timer
def speak(topic):
print "My speach is " + topic

speak("FP with Python")``````

# Functions

## Partial function application

The process of fixing a number of arguments to a function, producing another function of smaller arity

### Simply-typed lambda calculus:

`papply : (((a × b) → c) × a) → (b → c) = λ(f, x). λy. f (x, y)`

Oh, never mind...

## Partial function application

``````def log(level, message):
print "[{level}]: {msg}".format(level=level, msg=message)

log("debug", "Start doing something")
log("debug", "Continue with something else")
log("debug", "Finished. Profit?")

def debug(message):
log("debug", message)``````

## Partial function application

Simplify...

``````def log(level, message):
print "[{level}]: {msg}".format(level=level, msg=message)

from functools import partial
debug = partial(log, "debug")

debug("Start doing something")
debug("Continue with something else")
debug("Finished. Profit?")``````

## Currying

The technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument

### Simply-typed lambda calculus:

`curry: ((a × b) → c) → (a → (b → c)) = λf. λx. λy. f (x, y)`

Oh, never mind...

## Currying

Segment sum

``````def simple_sum(a, b):
return sum(range(a, b+1))

>>> simple_sum(1, 10)
55``````

## Currying

Squares

``````def square_sum(a, b):
return sum(map(lambda x: x**2, range(a,b+1)))

>>> square_sum(1,10)
385``````

## Currying

Logarithms

``````def log_sum(a, b):
return sum(map(math.log, range(a,b+1)))

>>> log_sum(1,10)
15.104412573075518``````

## Currying

In general...

``````def fsum(f):
def apply(a, b):
return sum(map(f, range(a,b+1)))
return apply

log_sum = fsum(math.log)
square_sum = fsum(lambda x: x**2)
simple_sum = fsum(int) ## fsum(lambda x: x)``````

``````>>> fsum(lambda x: x*2)(1, 10)
110
>>> import functools
>>> fsum(functools.partial(operator.mul, 2))(1, 10)
110``````

## Currying (standard library)

``````>>> from operator import itemgetter
>>> itemgetter(3)([1,2,3,4,5])
4

>>> from operator import attrgetter as attr
>>> class Speaker(object):
...     def __init__(self, name):
...         self.name = "[name] " + name
...
>>> alexey = Speaker("Alexey")
>>> attr("name")(alexey)
'[name] Alexey'``````

## Currying (standard library)

``````>>> from operator import methodcaller

>>> methodcaller("__str__")([1,2,3,4,5])
'[1, 2, 3, 4, 5]'
>>> methodcaller("keys")(dict(name="Alexey", topic="FP"))
['topic', 'name']

>>> values_extractor = methodcaller("values")
>>> values_extractor(dict(name="Alexey", topic="FP"))
['FP', 'Alexey']

>>> methodcaller("count", 1)([1,1,1,2,2])
>>> # same as [1,1,1,2,2].count(1)
3``````

## Good function is small function

``````>>> ss = ["UA", "PyCon", "2012"]
>>> reduce(lambda acc, s: acc + len(s), ss, 0)
11``````

``````>>> ss = ["UA", "PyCon", "2012"]
>>> reduce(lambda l,r: l+r, map(lambda s: len(s), ss))
11``````

### Good

``````>>> ss = ["UA", "PyCon", "2012"]
11``````

## Python hints

### types are callable

``````>>> map(str, range(5))
['0', '1', '2', '3', '4']``````

### classes are callable

``````>>> class Speaker(object):
...     def __init__(self, name):
...         self.name = name
>>> map(Speaker, ["Alexey", "Andrey", "Vsevolod"])
[<__main__.Speaker>, <__main__.Speaker>, <__main__.Speaker>]``````

### instance methods are callable

``````>>> map([1,2,3,4,5].count, [1,2,3,10,11])
[1, 1, 1, 0, 0]``````

### Pure

``````def is_interesting(topic):

### Not pure

``````def speak(topic):
print topic``````

### Pure ??

``````def set_talk(speaker, topic):
speaker["talk"] = topic
return speaker``````

## Mutable data

### Global variable is evil

and everybody knows why

``````current_speaker = {name: "Alexey Kachayev", talk: "FP with Python"}

def quit(reason):
current_speaker = {name: "Andrey Svetlov"} # <-- this will fail
current_speaker["talk"] = "Oh, boring..." # <-- mutable state``````

## Mutable data

``````def run_conf():
speaker = {name: "Alexey Kachayev", talk: "FP with Python"}

print "{name}, I have question {question} about {talk}"

def quit(reason):
current_speaker["talk"] = "Oh, boring..." # <- same

name = lambda: speaker["name"]``````

## Purity is cool

• map can be pmap
• Less bugs
• Easier to test
• More ways to reuse

## Classes and OOP

### Mutability...

``````class Speaker(object):
def __init__(self, name, topic):
self.name = name
self.topic = topic

print "{name}, {q}".format(name=self.name, q=question)

def talk(self):
print "I'm starting {topic}".format(topic=self.topic)

me = Speaker("Alexey", "FP with Python")
me.name = "Andrey" # <- WTF???

# or ....

me.set_name("Vsevolod") # <- guys, are you serious???``````

## Think functional: Classes and OOP

### Mutable dict + partial binding

``````def ask(self, question):
print "{name}, {q}?".format(name=self["name"], q=question)

def talk(self):
print "I'm starting {topic}".format(topic=self["topic"])

from functools import partial
def cls(**methods):
def bind(self):
return lambda (name, method): (name, partial(method, self))
return lambda **attrs: dict(
attrs.items() + map(bind(attrs.copy()), methods.items())
)

``````

## Think functional: Classes and OOP

``````>>> me = Speaker(name="Alexey", topic="FP with Python")

>>> me["name"]
'Alexey'
>>> me["topic"]
'FP with Python'
>>> me["talk"]
<functools.partial object at 0x109798d60>
>>> me["talk"]()
I'm starting FP with Python
<functools.partial object at 0x109798c58>
Alexey, WTF?``````

bindings are immutable

## Think functional: Classes and OOP

### If you need mutable implementation...

``````def cls(**methods):
def bind(**attrs):
attrs = attrs.copy()
attrs.update(dict(map(lambda (n,m): n, partial(m, attrs),
methods.items())))
return attrs
return bind

``````

## Stop writing classes

• Jack Diederich
• PyCon US 2012

## Stop writing classes

``````class Greeting(object):
def __init__(self, greeting="hello"):
self.greeting = greeting

def greet(self, name):
return "{greet}! {name}".format(greet=self.greeting, name)

hola = Greeting("hola")
print hola.greet("bob")

>>> "hola! bob"``````

## Stop writing classes

``````def greet(greeting, target):
return "{greet}! {name}".format(greet=greeting, name)

hola = functools.partial(greet, "hola")``````

## Stop writing classes ## Think functional: Data

### Assume that we don't have dict

``````def dct(*items):
def pair((key, value)):
return lambda k: value if k == key else None

def merge(l, r):
return lambda k: l(k) or r(k)

return reduce(merge, map(pair, items), pair((None, None)))``````

``````>>> me = dct(("name", "Alexey"), ("topic", "FP with Python"))
>>> me("name")
'Alexey'
>>> me("topic")
'FP with Python'
## use this for cls function
Alexey, WTF?
``````

## Python & FP

### Pro

• Functions as first-class citizens
• lambda
• Standard library: map/filter/reduce, itertools, operator
• Generators can be used for lazy-evaluation (in some cases)

## Python & FP

### Con

• Impossible to separate pure / non-pure
• Mutable variables
• Costly mem copy operations

## Python & FP

### Con

• Imperative style for cycles
• No optimization for tail recursion

## Python & FP

### Con

• No pattern matching syntax
• Classes-based only type system
• Functions composition is not implemented in stdlib
• Imperative errors handling based on exceptions

## Python & FP

### Python

``````map(lambda x: x*2, [1,2,3])
``````

### Scala

``````List(1,2,3).map(_*2)
``````

### Clojure

``````(map #(* % 2) '(1 2 3))
``````

``````map (2*) [1,2,3]
``````

## What did we miss?

### Almost everything

• Errors handling without exceptions
• Pattern matching
• Message passing
• Functional data structures
• Custom data types
• Lazy evaluation

## Where can I find more?

• SICP (http://deptinfo.unice.fr/~roy/sicp.pdf)
• Book "Purely Functional Data Structures"
• Book "The Functional Approach to Programming"
• Coursera "Functional Programming Principles in Scala"
• Learn You Some Erlang for Great Good! (http://learnyousomeerlang.com/)

## The end

### Thank you for attention!

• Alexey Kachayev
• Email: kachayev@gmail.com