Functional programming in Python (operator, functional, itertoools, toolz)

  • Pure functions

  • Recursive functions

  • Anonymous functions

  • Lazy evaluation

  • Higher-order functions

  • Decorators

  • Partial application

  • Using operator

  • Using functional

  • Using itertools

  • Pipelines with toolz

[1]:
import numpy as np

Pure functions

Deterministic

Pure

[2]:
np.exp(5), np.exp(5)
[2]:
(148.4131591025766, 148.4131591025766)

Not pure

[3]:
np.random.randn(), np.random.randn()
[3]:
(-0.07465802214544887, 1.0829226355933053)

No side effects

Pure

[4]:
def f(xs):
    '''Modify value at first index.'''
    if len(xs) > 0:
        xs = list(xs)
        xs[0] = '@'
    return xs
[5]:
xs = [1,2,3]
f(xs), xs
[5]:
(['@', 2, 3], [1, 2, 3])

Not pure

[6]:
def g(xs):
    '''Modify value at first index.'''
    if len(xs) > 0:
        xs[0] = '@'
    return xs
[7]:
xs = [1,2,3]
g(xs), xs
[7]:
(['@', 2, 3], ['@', 2, 3])

Exercise

Is the function h pure or impure?

[8]:
def h(n, xs=[]):
    for i in range(n):
        xs.append(i)
    return xs

The function is not deterministic, and it has side effects!

[9]:
n = 5
xs = [1,2,3]

Non-deterministic

[10]:
h(n)
[10]:
[0, 1, 2, 3, 4]
[11]:
h(n)
[11]:
[0, 1, 2, 3, 4, 0, 1, 2, 3, 4]

To avoid non-determinism, do not set default mutable arguments. The usaal Python idiom is

def func(xs=None):
    """Docstring."""

    if xs is None:
        xs = []
    do_something(xs)

Side effects

[12]:
xs = [1,2,3]
[13]:
h(n, xs)
[13]:
[1, 2, 3, 0, 1, 2, 3, 4]
[14]:
xs
[14]:
[1, 2, 3, 0, 1, 2, 3, 4]

Recursive functions

A recursive function is one that calls itself. Python supports recursion, but recursive functions in Python are not efficient and iterative algorithms are preferred in general.

[15]:
def rec_sum(xs):
    """Recursive sum."""

    if len(xs) == 0:
        return 0
    else:
        return xs[0] + rec_sum(xs[1:])
[16]:
rec_sum([1,2,3,4])
[16]:
10

Anonymous functions

[17]:
lambda x, y: x + y
[17]:
<function __main__.<lambda>(x, y)>
[18]:
add = lambda x, y: x + y
[19]:
add(3, 4)
[19]:
7
[20]:
lambda x, y: x if x < y else y
[20]:
<function __main__.<lambda>(x, y)>
[21]:
smaller = lambda x, y: x if x < y else y
[22]:
smaller(9,1)
[22]:
1

Lazy evaluation

[23]:
range(10)
[23]:
range(0, 10)
[24]:
list(range(10))
[24]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Generators

Generators behave like functions that retain the last state and can be re-entered. Results are returned with yield rather than return. Generators are used extensively in Python, and almost exclusively in the itertools and toolz packages we will review later in this notebook.

Differences between a function and a generator

[25]:
def fib_eager(n):
    """Eager Fibonacci function."""

    xs = []
    a, b = 1,1
    for i in range(n):
        xs.append(a)
        a, b = b, a + b
    return xs
[26]:
fib_eager(10)
[26]:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[27]:
def fib_lazy(n):
    """Lazy Fibonacci generator."""

    a, b = 1,1
    for i in range(n):
        yield a
        a, b = b, a + b
[28]:
fib_lazy(10)
[28]:
<generator object fib_lazy at 0x117053250>
[29]:
list(fib_lazy(10))
[29]:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[30]:
fibs1 = fib_eager(10)
[31]:
for i in fibs1:
    print(i, end=',')
1,1,2,3,5,8,13,21,34,55,
[32]:
for i in fibs1:
    print(i, end=',')
1,1,2,3,5,8,13,21,34,55,
[33]:
fibs2 = fib_lazy(10)
[34]:
for i in fibs2:
    print(i, end=',')
1,1,2,3,5,8,13,21,34,55,
[35]:
for i in fibs2:
    print(i, end=',')

Generators can return infinite sequences

[36]:
def iota(start = 1):
    """An infinite incrementing genrator."""

    while True:
        yield start
        start += 1
[37]:
for i in iota():
    print(i, end=',')
    if i > 25:
        break
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,

Higher order functions

  • Take a function as an argument

  • Returns a function

[38]:
def dist(x, y, measure):
    """Returns distance between x and y using given measure.

    measure is a function that takes two arguments x and y.
    """

    return measure(x, y)
[39]:
def euclid(x, y):
    """Returns Euclidean distance between x and y."""

    return np.sqrt(np.sum(x**2 + y**2))
[40]:
x = np.array([0,0])
y = np.array([3,4])

dist(x, y, measure=euclid)
[40]:
5.0

Standard HOFs

[41]:
from functools import reduce
[42]:
list(map(lambda x: x**2, range(10)))
[42]:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
[43]:
list(filter(lambda x: x % 2 == 0, range(10)))
[43]:
[0, 2, 4, 6, 8]
[44]:
reduce(lambda x, y: x + y, range(10))
[44]:
45
[45]:
reduce(lambda x, y: x + y, range(10), 10)
[45]:
55

Example: Flattening a nested list

[46]:
s1 = 'the quick brown fox'
s2 = 'jumps over the dog'
xs = [s.split() for s in [s1, s2]]
xs
[46]:
[['the', 'quick', 'brown', 'fox'], ['jumps', 'over', 'the', 'dog']]

Using a nested for loop

[47]:
ys = []
for x in xs:
    for y in x:
        ys.append(y)
ys
[47]:
['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'dog']

Using a list comprehension

[48]:
[y for x in xs for y in x]
[48]:
['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'dog']

Using reduce

[49]:
reduce(lambda x, y: x + y, xs)
[49]:
['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'dog']

Closure

[50]:
def f(a):
    """The argument given to f is visible in g when g is called."""

    def g(b):
        return a + b
    return g
[51]:
g3 = f(3)
g5 = f(5)
[52]:
g3(4), g5(4)
[52]:
(7, 9)

Decorators

A decorator is a higher-order function that takes a function as input and returns a decorated version of the original function with additional capabilities. There is syntactical sugar for decorators in Python using the @decorator_function notation as shown below.

[53]:
import time
[54]:
def timer(f):
    """Times how long f takes."""

    def g(*args, **kwargs):

        start = time.time()
        res = f(*args, **kwargs)
        elapsed = time.time() - start
        return res, elapsed
    return g
[55]:
def slow(n=1):
    time.sleep(n)
    return n

Use as a function

[56]:
slow_t1 = timer(slow)
[57]:
slow_t1(0.5)
[57]:
(0.5, 0.500197172164917)

Use as a decorator

[58]:
@timer
def slow_t2(n=1):
    time.sleep(n)
    return n
[59]:
slow_t2(0.5)
[59]:
(0.5, 0.5045151710510254)

Partial application

Partial application takes a function with two or more parameters, and returns the function with some parameters filled in. Partial application is very useful when constructing pipelines that transform data in stages.

[60]:
from functools import partial
[61]:
def add(a, b):
    """Add a and b."""

    return a + b
[62]:
list(map(partial(add, b=10), range(5)))
[62]:
[10, 11, 12, 13, 14]

Using operator

Operator provides named version of Python operators, and is typically used in place of anonymous functions in higher order functions to improve readability.

[63]:
import operator as op
[64]:
xs = [('a', 3), ('b', 1), ('c', 2)]
[65]:
sorted(xs, key=op.itemgetter(1))
[65]:
[('b', 1), ('c', 2), ('a', 3)]
[66]:
sorted(xs, key=lambda x: x[1])
[66]:
[('b', 1), ('c', 2), ('a', 3)]
[67]:
reduce(op.add, range(1,5))
[67]:
10
[68]:
reduce(lambda a, b: a + b, range(1,5))
[68]:
10

Using functional

We have already seen the use of reduce and partial from functools. Another useful function from the package is the lrucache decorator.

[69]:
def fib(n):
    """Recursive version of Fibonacci."""

    print('Call fib(%d)' % n)

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-2) + fib(n-1)

Notice the inefficiency from repeatedly calling the function with the same arguments.

[70]:
fib(6)
Call fib(6)
Call fib(4)
Call fib(2)
Call fib(0)
Call fib(1)
Call fib(3)
Call fib(1)
Call fib(2)
Call fib(0)
Call fib(1)
Call fib(5)
Call fib(3)
Call fib(1)
Call fib(2)
Call fib(0)
Call fib(1)
Call fib(4)
Call fib(2)
Call fib(0)
Call fib(1)
Call fib(3)
Call fib(1)
Call fib(2)
Call fib(0)
Call fib(1)
[70]:
8
[71]:
from functools import lru_cache
[72]:
@lru_cache(maxsize=None)
def fib_cache(n):
    """Recursive version of Fibonacci."""

    print('Call fib(%d)' % n)

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_cache(n-2) + fib_cache(n-1)
[73]:
fib_cache(6)
Call fib(6)
Call fib(4)
Call fib(2)
Call fib(0)
Call fib(1)
Call fib(3)
Call fib(5)
[73]:
8

Using itertools

The itertools package provides tools for efficient looping.

[74]:
import itertools as it

Generators

[75]:
list(it.islice(it.count(), 10))
[75]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[76]:
list(it.islice(it.cycle([1,2,3]), 10))
[76]:
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1]
[77]:
list(it.islice(it.repeat([1,2,3]), 10))
[77]:
[[1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3],
 [1, 2, 3]]
[78]:
list(it.zip_longest(range(5), 'abc'))
[78]:
[(0, 'a'), (1, 'b'), (2, 'c'), (3, None), (4, None)]
[79]:
list(it.zip_longest(range(5), 'abc', fillvalue='out of donuts'))
[79]:
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'out of donuts'), (4, 'out of donuts')]

Permutations and combinations

[80]:
list(it.permutations('abc'))
[80]:
[('a', 'b', 'c'),
 ('a', 'c', 'b'),
 ('b', 'a', 'c'),
 ('b', 'c', 'a'),
 ('c', 'a', 'b'),
 ('c', 'b', 'a')]
[81]:
list(it.permutations('abc', 2))
[81]:
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
[82]:
list(it.combinations('abc', 2))
[82]:
[('a', 'b'), ('a', 'c'), ('b', 'c')]
[83]:
list(it.combinations_with_replacement('abc', 2))
[83]:
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]
[84]:
list(it.product('abc', repeat=2))
[84]:
[('a', 'a'),
 ('a', 'b'),
 ('a', 'c'),
 ('b', 'a'),
 ('b', 'b'),
 ('b', 'c'),
 ('c', 'a'),
 ('c', 'b'),
 ('c', 'c')]

Miscellaneous

[85]:
list(it.chain([1,2,3], [4,5,6], [7,8,9]))
[85]:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[86]:
list(it.chain.from_iterable([[1,2,3], [4,5,6], [7,8,9]]))
[86]:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[87]:
nums = [1,3,5,7,2,4,6,1,3,5,7,9,2,2,2]
[88]:
for i, g in it.groupby(nums, key=lambda x: x % 2 ==0):
    print(i, list(g))
False [1, 3, 5, 7]
True [2, 4, 6]
False [1, 3, 5, 7, 9]
True [2, 2, 2]
[89]:
list(it.takewhile(lambda x: x % 2 == 1, nums))
[89]:
[1, 3, 5, 7]
[90]:
list(it.dropwhile(lambda x: x % 2 == 1, nums))
[90]:
[2, 4, 6, 1, 3, 5, 7, 9, 2, 2, 2]

Using toolz

The toolz package provides a very rich set of functional operators, and is recommended if you want to program in the functional style using Python.

[91]:
import toolz
[92]:
from toolz import sliding_window, pipe, frequencies, concat
[93]:
import toolz.curried as c

Example: Read in some documents, remove punctuation, split into words and then into individual characters, and find the most commonly occurring sliding windows containing 3 characters.

This is most naturally done by piping in a data set through a series of transforms.

[94]:
d1 = 'the doo doo doo the dah dah dah'
d2 = 'every breath she takes, every move she makes'
d3 = 'another brick in the wall'
d4 = 'another one bites the dust and another one gone'
docs = [d1,d2,d3,d4]
[95]:
import string
[126]:
triple_freqs = pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    c.map(lambda x: ''.join(x)),
    frequencies,
)
[127]:
sorted(triple_freqs.items(), key=lambda x: x[1], reverse=True)[:5]
[127]:
[('the', 7), ('oth', 4), ('hed', 3), ('doo', 3), ('dah', 3)]

Step by step

[130]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    c.map(lambda x: ''.join(x)),
    frequencies,
)
[130]:
{'the': 7,
 'hed': 3,
 'edo': 1,
 'doo': 3,
 'ood': 2,
 'odo': 2,
 'oot': 1,
 'oth': 4,
 'eda': 1,
 'dah': 3,
 'ahd': 2,
 'hda': 2,
 'ahe': 1,
 'hev': 1,
 'eve': 2,
 'ver': 2,
 'ery': 2,
 'ryb': 1,
 'ybr': 1,
 'bre': 1,
 'rea': 1,
 'eat': 1,
 'ath': 1,
 'ths': 1,
 'hsh': 1,
 'she': 2,
 'het': 1,
 'eta': 1,
 'tak': 1,
 'ake': 2,
 'kes': 2,
 'ese': 1,
 'sev': 1,
 'rym': 1,
 'ymo': 1,
 'mov': 1,
 'ove': 1,
 'ves': 1,
 'esh': 1,
 'hem': 1,
 'ema': 1,
 'mak': 1,
 'esa': 1,
 'san': 1,
 'ano': 3,
 'not': 3,
 'her': 3,
 'erb': 1,
 'rbr': 1,
 'bri': 1,
 'ric': 1,
 'ick': 1,
 'cki': 1,
 'kin': 1,
 'int': 1,
 'nth': 1,
 'hew': 1,
 'ewa': 1,
 'wal': 1,
 'all': 1,
 'lla': 1,
 'lan': 1,
 'ero': 2,
 'ron': 2,
 'one': 3,
 'neb': 1,
 'ebi': 1,
 'bit': 1,
 'ite': 1,
 'tes': 1,
 'est': 1,
 'sth': 1,
 'edu': 1,
 'dus': 1,
 'ust': 1,
 'sta': 1,
 'tan': 1,
 'and': 1,
 'nda': 1,
 'dan': 1,
 'neg': 1,
 'ego': 1,
 'gon': 1}
[131]:
pipe(
    docs,
    list
)
[131]:
['the doo doo doo the dah dah dah',
 'every breath she takes, every move she makes',
 'another brick in the wall',
 'another one bites the dust and another one gone']
[132]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    list
)
[132]:
['the doo doo doo the dah dah dah',
 'every breath she takes every move she makes',
 'another brick in the wall',
 'another one bites the dust and another one gone']
[133]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    list
)
[133]:
[['the', 'doo', 'doo', 'doo', 'the', 'dah', 'dah', 'dah'],
 ['every', 'breath', 'she', 'takes', 'every', 'move', 'she', 'makes'],
 ['another', 'brick', 'in', 'the', 'wall'],
 ['another', 'one', 'bites', 'the', 'dust', 'and', 'another', 'one', 'gone']]
[134]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    c.take(5),
    list
)
[134]:
['the', 'doo', 'doo', 'doo', 'the']
[135]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.take(5),
    list
)
[135]:
['t', 'h', 'e', 'd', 'o']
[136]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    c.take(5),
    list
)
[136]:
[('t', 'h', 'e'),
 ('h', 'e', 'd'),
 ('e', 'd', 'o'),
 ('d', 'o', 'o'),
 ('o', 'o', 'd')]
[140]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    c.map(lambda x: ''.join(x)),
    c.take(10),
    list
)
[140]:
['the', 'hed', 'edo', 'doo', 'ood', 'odo', 'doo', 'ood', 'odo', 'doo']
[139]:
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    c.map(lambda x: ''.join(x)),
    frequencies
)
[139]:
{'the': 7,
 'hed': 3,
 'edo': 1,
 'doo': 3,
 'ood': 2,
 'odo': 2,
 'oot': 1,
 'oth': 4,
 'eda': 1,
 'dah': 3,
 'ahd': 2,
 'hda': 2,
 'ahe': 1,
 'hev': 1,
 'eve': 2,
 'ver': 2,
 'ery': 2,
 'ryb': 1,
 'ybr': 1,
 'bre': 1,
 'rea': 1,
 'eat': 1,
 'ath': 1,
 'ths': 1,
 'hsh': 1,
 'she': 2,
 'het': 1,
 'eta': 1,
 'tak': 1,
 'ake': 2,
 'kes': 2,
 'ese': 1,
 'sev': 1,
 'rym': 1,
 'ymo': 1,
 'mov': 1,
 'ove': 1,
 'ves': 1,
 'esh': 1,
 'hem': 1,
 'ema': 1,
 'mak': 1,
 'esa': 1,
 'san': 1,
 'ano': 3,
 'not': 3,
 'her': 3,
 'erb': 1,
 'rbr': 1,
 'bri': 1,
 'ric': 1,
 'ick': 1,
 'cki': 1,
 'kin': 1,
 'int': 1,
 'nth': 1,
 'hew': 1,
 'ewa': 1,
 'wal': 1,
 'all': 1,
 'lla': 1,
 'lan': 1,
 'ero': 2,
 'ron': 2,
 'one': 3,
 'neb': 1,
 'ebi': 1,
 'bit': 1,
 'ite': 1,
 'tes': 1,
 'est': 1,
 'sth': 1,
 'edu': 1,
 'dus': 1,
 'ust': 1,
 'sta': 1,
 'tan': 1,
 'and': 1,
 'nda': 1,
 'dan': 1,
 'neg': 1,
 'ego': 1,
 'gon': 1}
[ ]: