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

import numpy as np

Pure functions

Deterministic

Pure

np.exp(5), np.exp(5)

(148.4131591025766, 148.4131591025766)

Not pure

np.random.randn(), np.random.randn()

(-0.07465802214544887, 1.0829226355933053)

No side effects

Pure

def f(xs):
    '''Modify value at first index.'''
    if len(xs) > 0:
        xs = list(xs)
        xs[0] = '@'
    return xs

xs = [1,2,3]
f(xs), xs

(['@', 2, 3], [1, 2, 3])

Not pure

def g(xs):
    '''Modify value at first index.'''
    if len(xs) > 0:
        xs[0] = '@'
    return xs

xs = [1,2,3]
g(xs), xs

(['@', 2, 3], ['@', 2, 3])

Exercise

Is the function h pure or impure?

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

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

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

Non-deterministic

h(n)

[0, 1, 2, 3, 4]

h(n)

[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

xs = [1,2,3]

h(n, xs)

[1, 2, 3, 0, 1, 2, 3, 4]

xs

[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.

def rec_sum(xs):
    """Recursive sum."""

    if len(xs) == 0:
        return 0
    else:
        return xs[0] + rec_sum(xs[1:])

rec_sum([1,2,3,4])

10

Anonymous functions

lambda x, y: x + y

<function __main__.<lambda>(x, y)>

add = lambda x, y: x + y

add(3, 4)

7

lambda x, y: x if x < y else y

<function __main__.<lambda>(x, y)>

smaller = lambda x, y: x if x < y else y

smaller(9,1)

1

Lazy evaluation

range(10)

range(0, 10)

list(range(10))

[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

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

fib_eager(10)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

def fib_lazy(n):
    """Lazy Fibonacci generator."""

    a, b = 1,1
    for i in range(n):
        yield a
        a, b = b, a + b

fib_lazy(10)

<generator object fib_lazy at 0x117053250>

list(fib_lazy(10))

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

fibs1 = fib_eager(10)

for i in fibs1:
    print(i, end=',')

1,1,2,3,5,8,13,21,34,55,

for i in fibs1:
    print(i, end=',')

1,1,2,3,5,8,13,21,34,55,

fibs2 = fib_lazy(10)

for i in fibs2:
    print(i, end=',')

1,1,2,3,5,8,13,21,34,55,

for i in fibs2:
    print(i, end=',')

Generators can return infinite sequences

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

    while True:
        yield start
        start += 1

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

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)

def euclid(x, y):
    """Returns Euclidean distance between x and y."""

    return np.sqrt(np.sum(x**2 + y**2))

x = np.array([0,0])
y = np.array([3,4])

dist(x, y, measure=euclid)

5.0

Standard HOFs

from functools import reduce

list(map(lambda x: x**2, range(10)))

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

list(filter(lambda x: x % 2 == 0, range(10)))

[0, 2, 4, 6, 8]

reduce(lambda x, y: x + y, range(10))

45

reduce(lambda x, y: x + y, range(10), 10)

55

Example: Flattening a nested list

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

[['the', 'quick', 'brown', 'fox'], ['jumps', 'over', 'the', 'dog']]

Using a nested for loop

ys = []
for x in xs:
    for y in x:
        ys.append(y)
ys

['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'dog']

Using a list comprehension

[y for x in xs for y in x]

['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'dog']

Using reduce

reduce(lambda x, y: x + y, xs)

['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'dog']

Closure

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

    def g(b):
        return a + b
    return g

g3 = f(3)
g5 = f(5)

g3(4), g5(4)

(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.

import time

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

def slow(n=1):
    time.sleep(n)
    return n

Use as a function

slow_t1 = timer(slow)

slow_t1(0.5)

(0.5, 0.500197172164917)

Use as a decorator

@timer
def slow_t2(n=1):
    time.sleep(n)
    return n

slow_t2(0.5)

(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.

from functools import partial

def add(a, b):
    """Add a and b."""

    return a + b

list(map(partial(add, b=10), range(5)))

[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.

import operator as op

xs = [('a', 3), ('b', 1), ('c', 2)]

sorted(xs, key=op.itemgetter(1))

[('b', 1), ('c', 2), ('a', 3)]

sorted(xs, key=lambda x: x[1])

[('b', 1), ('c', 2), ('a', 3)]

reduce(op.add, range(1,5))

10

reduce(lambda a, b: a + b, range(1,5))

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.

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.

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)

8

from functools import lru_cache

@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)

fib_cache(6)

Call fib(6)
Call fib(4)
Call fib(2)
Call fib(0)
Call fib(1)
Call fib(3)
Call fib(5)

8

Using itertools

The itertools package provides tools for efficient looping.

import itertools as it

Generators

list(it.islice(it.count(), 10))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

list(it.islice(it.cycle([1,2,3]), 10))

[1, 2, 3, 1, 2, 3, 1, 2, 3, 1]

list(it.islice(it.repeat([1,2,3]), 10))

[[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]]

list(it.zip_longest(range(5), 'abc'))

[(0, 'a'), (1, 'b'), (2, 'c'), (3, None), (4, None)]

list(it.zip_longest(range(5), 'abc', fillvalue='out of donuts'))

[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'out of donuts'), (4, 'out of donuts')]

Permutations and combinations

list(it.permutations('abc'))

[('a', 'b', 'c'),
 ('a', 'c', 'b'),
 ('b', 'a', 'c'),
 ('b', 'c', 'a'),
 ('c', 'a', 'b'),
 ('c', 'b', 'a')]

list(it.permutations('abc', 2))

[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

list(it.combinations('abc', 2))

[('a', 'b'), ('a', 'c'), ('b', 'c')]

list(it.combinations_with_replacement('abc', 2))

[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]

list(it.product('abc', repeat=2))

[('a', 'a'),
 ('a', 'b'),
 ('a', 'c'),
 ('b', 'a'),
 ('b', 'b'),
 ('b', 'c'),
 ('c', 'a'),
 ('c', 'b'),
 ('c', 'c')]

Miscellaneous

list(it.chain([1,2,3], [4,5,6], [7,8,9]))

[1, 2, 3, 4, 5, 6, 7, 8, 9]

list(it.chain.from_iterable([[1,2,3], [4,5,6], [7,8,9]]))

[1, 2, 3, 4, 5, 6, 7, 8, 9]

nums = [1,3,5,7,2,4,6,1,3,5,7,9,2,2,2]

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]

list(it.takewhile(lambda x: x % 2 == 1, nums))

[1, 3, 5, 7]

list(it.dropwhile(lambda x: x % 2 == 1, nums))

[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.

import toolz

from toolz import sliding_window, pipe, frequencies, concat

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.

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]

import string

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,
)

sorted(triple_freqs.items(), key=lambda x: x[1], reverse=True)[:5]

[('the', 7), ('oth', 4), ('hed', 3), ('doo', 3), ('dah', 3)]

Step by step

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,
)

{'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}

pipe(
    docs,
    list
)

['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']

pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    list
)

['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']

pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    list
)

[['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']]

pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    c.take(5),
    list
)

['the', 'doo', 'doo', 'doo', 'the']

pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.take(5),
    list
)

['t', 'h', 'e', 'd', 'o']

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
)

[('t', 'h', 'e'),
 ('h', 'e', 'd'),
 ('e', 'd', 'o'),
 ('d', 'o', 'o'),
 ('o', 'o', 'd')]

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
)

['the', 'hed', 'edo', 'doo', 'ood', 'odo', 'doo', 'ood', 'odo', 'doo']

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
)

{'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}