andy.md

Functional Programming Exercises

Some terminology

When writing code in python, we're used to calling things functions when in reality what we're writing are procedures.

What's the difference?

Procedures and Functions

A procedure is a well defined sequence of instructions for performing a computational task. A compiler will take that procedure and translate it to procedures made up of even more primitive operations that can be run natively by a CPU.

Some procedures have side-effects that determine their output. One such side-effect could be modifying a global counter

counter = 0

def get_count():
    global counter
    counter += 1
    return counter

another side-effect could be opening a file

def read_file():
    with open("file.txt") as f:
        return f.read()

or a myriad other things.

There is a particular class of procedures with outputs that are strictly determined by their inputs.

These procedures are realizations of functions (in the mathematical sense of the word) so for that reason we call them functions.

Scoping

When writing functions it's important to understand how variables are scoped, that is to say how the value of a variable will differ depending on the context in which it's evaluated, and the rules that govern what contexts exist.

As a simple example, if you try to run the get_count function above without the explicit global declaration, you will see an exception

>>> counter = 0
>>>
>>> def get_count():
...     counter += 1
...     return counter
...
>>> get_count()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
    File "<stdin>", line 2, in get_count
	UnboundLocalError: local variable 'counter' referenced before assignment

This is because the get_count procedure runs in a different scope from the global one. Adding the global counter statement tells the interpreter that it should get and modify the counter variable that is in the global scope in stead of the non-existent one in the function's scope.

Likewise if you were to not use global and set the value of counter inside of the function you would only change the value of counter inside the scope of the function

counter = 1
def get_count():
    counter = 2
    print counter

get_count()
print counter

will print

2
1

This policy of scoping procedures separately is referred to as lexical scoping and its opposite of having just a single global scope for all procedures is called dynamic scoping.

Ok, so now we know there's a different scope created for every execution of a procedure which is how you have functions. Consider the simple parity checker function

def is_odd(n):
    return bool(n % 2)

Because n is scoped differently per execution of the procedure you could have multiple concurrent executions that wouldn't confuse each other by reading each other's value for n.

Now things get interesting when you start to nest scopes. Scope nesting basically creates different variable scopes such that the inner-most scope has all of its own variables plus all of the variables of its outer scope. This can theoretically be done to an nth degree but usually only goes one level deep. To see when this is relevant, let's meet an interesting class of functions called functionals.

Functionals

Some functions themselves take functions as inputs and produce functions as outputs. In math and in computer science we call these higher-order constructs functionals.

As an example, there's the composition operation:

def compose(f, g):
    def composition(n):
        return f(g(n))
    return composition

which we could use to make an is_even function using our is odd function and a successor function

successor = lambda n: n + 1
is_even = compose(is_odd, successor)

Now let's carefully see what we've done. Remember that a new scope is created whenever you execute a function. So when you call compose(is_odd, successor) you make the scope

f -> is_odd
g -> successor

because f and g are parameters to compose for which is_odd and successor are the corresponding actual argument values. Within this same scope you define composition

f           -> is_odd
g           -> successor
composition -> <some function>

and it's important to note that when composition (which gets assigned to even in the global scope) executes, it will do so in a nested scope of this original scope.

This is why the body of composition can reference f and g. This is also why you could call compose multiple times and create new functions.

Functions in more depth

Scope nesting is tricky but essential part of functional programming. The best way is to play around with it until you get it.

To get started, let's consider the essential property of functions. They always map the same input to the same output. Once your procedure has calculated a particular output, it can store the input-output mapping in a look-up table. The next time the same input comes in, the procedure can first check the look-up table and output the value if it is there. Doing so is often more efficient than computing the output again. We call this technique memoization and it becomes invaluable when writing recursive procedures.

Consider these two implementations for outputting the nth fibonacci number

def fib1(n):
    if n in [0, 1]:
        return 1
    return fib1(n - 1) + fib1(n - 2)

lookup = {}
def fib2(n):
    global lookup
    if n in lookup:
        return lookup[n]
    if n in [0, 1]:
        out = 1
    else:
        out = fib2(n - 1) + fib2(n - 2)
    lookup[n] = out
    return out

fib1 will actually have to do on the order of a*2^n steps whereas fib2 will have to do approximately b*n steps where a and b are constants, which is a huge difference in performace.

Exercise

As an exercise, at this point you should try to write a memoized version of primelist.

Decorators

Now we'll meet a special kind of functional called a decorator. Decorators let you annotate your functions with useful phrases that let the compiler know to run your function with some transformation applied to it. A decorator takes in a procedure as input and outputs the transformed procedure. This decorator for instance will wrap the function in useful loggin messages.

def log(f):
    def wrapper(n):
        print "Got input:", n
        out = f(n)
        print "Got output:", out
        return out
    return wrapper

And now we can apply this decorator to any function definition

@log
def is_odd(n):
    return bool(n % 2)

If you run is_odd(5) now you should see our debug logs.

Exercise

Write a @memoize decorator, that will take any monadic function (function with one parameter n) and turn it into a memoized function

Polyadic Decorators

Sometimes you want to write a decorator that can apply functions that have different signatures. Our logger for instance shouldn't care if the wrapped function has one parameter or two or three. Python has some special syntax that lets you take in any number of arguments as a tuple and any key-word arguments as a dict. To see this in action lets modify our logger,

def log(f):
    def wrapper(*args, **kwargs):
        print "Got input args:", args, "kwargs:", kwargs
        out = f(*args, **kwargs)
        print "Got output:", out
        return out
    return wrapper

and now if we redefine is_odd

@log
def is_odd(n):
    return bool(n % 2)

we'll see it still works.

Exercise

Now you should be able to make your memoize decorator above work on functions of any adicity.

Class Scopes

In object oriented programming languages, objects are usually the preferred mechanism for scoping rather than functions. Rather than create a different scope per function call, you create different objects that have attributes. Here's one that creates fibonnaci numbers using a lookup-table as one of its attributes

class FibGenerator(object):
    def __init__(self):
        self.lookup = {}

    def get_number(self, n):
        if n in self.lookup:
            return self.lookup[n]
        if n in [0, 1]:
            out = 1
        else:
            out = fib2(n - 1) + fib2(n - 2)
        lookup[n] = out
        return out

f = FibGenerator()
f.get_number(8)

Exercise

Can you now make a version of primelist that's memoized as an object?

Special method names

Python has a bunch of infix operators that work on objects like for addition 5 + 2, or for selecting elements l[i]. As it turns out you can override the behavior of these operators. We can for instance make the above FibGenerator into a list-like object which can calculate its own nth item just-in-time if it needs to

class FibList(object):
    def __init__(self):
        self.lookup = {}

    def __getitem__(self, n):
        if n in self.lookup:
            return self.lookup[n]
        if n in [0, 1]:
            out = 1
        else:
            out = fib2(n - 1) + fib2(n - 2)
        lookup[n] = out
        return out

f = FibList()
f[8]

Exercise

Can you make a just-in-time PrimeList?