<jupyter_start><jupyter_text>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`<jupyter_code>import numpy as np<jupyter_output><empty_output><jupyter_text>Everything in Python is an object. Can check properties / functions for the object by using tab after .However, most of what we need in stats can be accomplished through functional programming  Review of functions Every function that we write in this class must have a doc string, or we will lose points! At least include the one-line function summary<jupyter_code>def f(a, b, c=3):
    """First linee provides a one-line funciton summmary.
    
    Input:
    a: any
    b: any
    c: any
    
    Returns the tuple (a, b, c)
    """
    return (a, b, c)
f(4,5,6)
f(4,5)
f(c=3, b=2, a=1)
f(*[1,2,3])
# Recall, * expands a list
f(**dict(a=3, b= 2, c=1))
# ** expands a dictionary<jupyter_output><empty_output><jupyter_text>Annotations (aka type hints)Type hints indicate your intent, and may be used by 3rd party libraries for various purposes (e.g. auto-completion, type-safe warnings, auto-completion). Note that the Python interpreter does not enforce type hints.See [blog](http://veekaybee.github.io/2019/07/08/python-type-hints/) for more information.  Variable annotation<jupyter_code>a: int = 3
a<jupyter_output><empty_output><jupyter_text>Python is a dynamically-typed langugage. We won't use static typing in this course, but Prof Chan just wants to expose us to the concept  Function annotation<jupyter_code>from typing import Any, Tuple
# -> is type hint for return value from function
def g(a: Any, b: Any, c: Any = 3) -> Tuple[Any, Any, Any]:
    """Example showing function annotations."""
    
    return (a, b, c)
g(1, 2, 3)
g(a=3, b=2, c=1)
# Syntax to check annotations in global namespace
__annotations__
g.__annotations__<jupyter_output><empty_output><jupyter_text>Not enforced!<jupyter_code>def foo(a: int) -> int:
    return a * 3
foo('oops')<jupyter_output><empty_output><jupyter_text>Pure functions  Deterministic Pure - deterministic... will always give same response for a given argument. Does not have any side effects<jupyter_code>np.exp(5), np.exp(5)<jupyter_output><empty_output><jupyter_text>Not pure - anything that deals with randomness, not deterministic<jupyter_code>np.random.randn(), np.random.randn()<jupyter_output><empty_output><jupyter_text>No side effects Pure - helpful for parallel computing because all of the runs are independent<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Not pure - changes the input<jupyter_code>def g(xs):
    '''Modify value at first index.'''
    if len(xs) > 0:
        xs[0] = '@'
    return xs
xs = [1,2,3]
g(xs), xs<jupyter_output><empty_output><jupyter_text>ExerciseIs the function `h` pure or impure?<jupyter_code>def h(n, xs=[]):
    for i in range(n):
        xs.append(i)
    return xs<jupyter_output><empty_output><jupyter_text>The function is not deterministic, and it has side effects!<jupyter_code>n = 5
xs = [1,2,3]<jupyter_output><empty_output><jupyter_text>Non-deterministic<jupyter_code>h(n)
# Using xs from memory in previous function call
h(n)<jupyter_output><empty_output><jupyter_text>To avoid non-determinism, do not set default mutable arguments. The usual Python idiom is```pythondef func(xs=None):    """Docstring."""        if xs is None:        xs = []    do_something(xs)``` Side effects<jupyter_code>xs = [1,2,3]
h(n, xs)
xs<jupyter_output><empty_output><jupyter_text>Recursive functionsA 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. Can also have mutually recursive functions where a calls b and b calls aAllows for entirely pure function because there is no loop (in which loop counter would be changing)2 parts to recursive functions:- Base case (which has quick return)- Recursive portion<jupyter_code>def rec_sum(xs):
    """Recursive sum."""
    
    if len(xs) == 0:
        return 0
    else:
        return xs[0] + rec_sum(xs[1:]) # Remainder is simply empty list when numbers run out
rec_sum([1,2,3,4])<jupyter_output><empty_output><jupyter_text>Anonymous functions<jupyter_code>lambda x, y: x + y
# Assign anonymous function to name
add = lambda x, y: x + y
add(3, 4)
lambda x, y: x if x < y else y
smaller = lambda x, y: x if x < y else y
smaller(9,1)<jupyter_output><empty_output><jupyter_text>Lazy evaluation<jupyter_code>range(10)
list(range(10))<jupyter_output><empty_output><jupyter_text>GeneratorsGenerators 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<jupyter_code>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)
# Don't need to assign storage!
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)
list(fib_lazy(10))
fibs1 = fib_eager(10)
for i in fibs1:
    print(i, end=',')
for i in fibs1:
    print(i, end=',')
fibs2 = fib_lazy(10)
for i in fibs2:
    print(i, end=',')
# Doesn't print anything because all has been looped through in the previous for loop call!
# "Once you exhaust the generator, it won't return anything"
for i in fibs2:
    print(i, end=',')<jupyter_output><empty_output><jupyter_text>Generators can return infinite sequences<jupyter_code>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<jupyter_output>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,<jupyter_text>Higher order functionsDoes at least one of the following: - Take a function as an argument - Returns a function<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>Standard HOFs Map, filter, and reduce are 3 big higher order functions that we need to know<jupyter_code>from functools import reduce
# Map takes a function and applies it to every element of a collection
list(map(lambda x: x**2, range(10)))
# Filter takes a condition and only returns the elements which meet the condition
# Should always do this first
list(filter(lambda x: x % 2 == 0, range(10)))
# Reduce takes a collection and collapses it down
reduce(lambda x, y: x + y, range(10))
# Optional last argument is starting value for reduce
reduce(lambda x, y: x + y, range(10), 10)<jupyter_output><empty_output><jupyter_text>Example: Flattening a nested list<jupyter_code>s1 = 'the quick brown fox'
s2 = 'jumps over the dog'
xs = [s.split() for s in [s1, s2]]
xs<jupyter_output><empty_output><jupyter_text>Using a nested for loop<jupyter_code>ys = []
for x in xs:
    for y in x:
        ys.append(y)
ys<jupyter_output><empty_output><jupyter_text>Using a list comprehension<jupyter_code># Follows order of outer loop to inner loop
[y for x in xs for y in x]<jupyter_output><empty_output><jupyter_text>Using `reduce`<jupyter_code>reduce(lambda x, y: x + y, xs)<jupyter_output><empty_output><jupyter_text>Closure Higher order functions that return functions<jupyter_code>def f(a):
    """The argument given to f is visible in g when g is called."""
    
    def g(b):
        return a + b
    return g
# a is remembered by g when g is called later
g3 = f(3)
g5 = f(5)
g3(4), g5(4)<jupyter_output><empty_output><jupyter_text>DecoratorsA 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.<jupyter_code>import time
# Returns normal function output AND time elapsed
def timer(f):
    """Times how long f takes."""
    
    # Means g can take any arguments
    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<jupyter_output><empty_output><jupyter_text>Use as a function<jupyter_code>slow_t1 = timer(slow)
slow_t1(0.5)<jupyter_output><empty_output><jupyter_text>Use as a decorator<jupyter_code>@timer
def slow_t2(n=1):
    time.sleep(n)
    return n
slow_t2(0.5)<jupyter_output><empty_output><jupyter_text>Partial applicationPartial 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.<jupyter_code>from functools import partial
def add(a, b):
    """Add a and b."""
    
    return a + b
# Allows us to specify a default argument on the fly
list(map(partial(add, b=10), range(5)))
# Feeding two arguments to map
list(map(add, range(5), range(5)))<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>import operator as op
xs = [('a', 3), ('b', 1), ('c', 2)]
sorted(xs, key=op.itemgetter(1))
sorted(xs, key=lambda x: x[1])
reduce(op.add, range(1,5))
reduce(lambda a, b: a + b, range(1,5))<jupyter_output><empty_output><jupyter_text>Using `functional`We have already seen the use of `reduce` and `partial` from `functools`. Another useful function from the package is the `lrucache` decorator.lru is "least recently used"<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>Notice the inefficiency from repeatedly calling the function with the same arguments.<jupyter_code>%%time

fib(6)
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)
%%timeit

# Never calls the function with the same argument twice... much more efficient
fib_cache(6)<jupyter_output>117 ns ± 0.874 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)<jupyter_text>Using `itertools`The `itertools` package provides tools for efficient looping.<jupyter_code>import itertools as it<jupyter_output><empty_output><jupyter_text>Generators<jupyter_code># islice grabs a subset of otherwise infinite functions (e.g., it.count(), it.cycle())
list(it.islice(it.count(), 10))
list(it.islice(it.cycle([1,2,3]), 10))
list(it.islice(it.repeat([1,2,3]), 10))
# Standard zip will only work until the shortest element is exhausted
list(it.zip_longest(range(5), 'abc'))
# Specify fill value when lengths are not equal
list(it.zip_longest(range(5), 'abc', fillvalue='out of donuts'))<jupyter_output><empty_output><jupyter_text>Permutations and combinations<jupyter_code>np.random.permutation([1, 3, 5, 7])
np.random.permutation(10)
# Will sequentially go through all itertools
list(it.permutations('abc'))
list(it.permutations('abc', 2))
list(it.combinations('abc', 2))
list(it.combinations_with_replacement('abc', 2))
list(it.product('abc', repeat=2))<jupyter_output><empty_output><jupyter_text>Miscellaneous<jupyter_code>list(it.chain([1,2,3], [4,5,6], [7,8,9]))
list(it.chain.from_iterable([[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))
list(it.takewhile(lambda x: x % 2 == 1, nums))
list(it.dropwhile(lambda x: x % 2 == 1, nums))<jupyter_output><empty_output><jupyter_text>Example: Classic word-count using map-reduceThere are two basic steps - first we create a tuple (word, 1), then group by word, then reduce the grouping to sum up the ones.<jupyter_code>rhyme = 'humpty dumpty sat on a wall humpty dumpty had a great fall'
words = rhyme.split()
words<jupyter_output><empty_output><jupyter_text>Map to create key-value pair<jupyter_code>x1 = map(lambda x: (x, 1), words)
list(x1)<jupyter_output><empty_output><jupyter_text>Group similar keys together<jupyter_code>x2 = it.groupby(sorted(x1), key=lambda x: x[0])<jupyter_output><empty_output><jupyter_text>Reduce on value of key-value pair<jupyter_code>x3 = map(lambda x: (x[0], reduce(lambda a, b: a[1] + b[1], x[1])), x2)<jupyter_output><empty_output><jupyter_text>Clean-up because the nested reduce stops when the list has only one element<jupyter_code>x4 = map(lambda x: (x[0], x[1] if isinstance(x[1], int) else x[1][1]), x3)
list(x4)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>import toolz
from toolz import sliding_window, pipe, frequencies, concat
import toolz.curried as c<jupyter_output><empty_output><jupyter_text>Example word count revisited<jupyter_code>frequencies(words)<jupyter_output><empty_output><jupyter_text>ExampleRead 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.<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Currying allows us to take a function that would normally take multiple arguments and give it fewer than needed (at least to start). It is necessary to curry functions this pipe because map typically takes a function and a collection over which to apply the function. We don't have the collection to start because it needs to pass through earlier stages of the pipe first<jupyter_code>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),
    frequencies,
)
sorted(triple_freqs.items(), key=lambda x: x[1], reverse=True)[:5]<jupyter_output><empty_output><jupyter_text>Step by step<jupyter_code>pipe(
    docs,
    list # Allows us to see output after each step
)
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))), # c.map means that map only expects a function argument (takes input from previous step)
    list
)
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    list
)
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    list
)
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    list
)
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    list
)
pipe(
    docs,
    c.map(lambda x: x.translate(str.maketrans('', '', string.punctuation))),
    c.map(lambda x: x.split()),
    concat,
    concat,
    c.sliding_window(3),
    frequencies
)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11885072734955031, 'fraction_numerical': 0.019315506730246877, 'mean_word_length': 4.701307639366827, 'pattern_counts': {'":': 0, '<': 185, '<?xml version=': 0, '>': 189, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '46', 'dir': 'jupyter-structured-clean-dedup', 'id': '46752', 'license': 'MIT', 'n_tokens_mistral': 5878, 'n_tokens_neox': 5618, 'n_words': 1780, 'path': 'notebooks/copies/lectures/S06_Functional.ipynb', 'repo_name': 'robkravec/sta-663-2021', 'size': '16567'}