Functional Programming

Functions are values

In imperative programming, a program is a sequence of commands that change variables. In functional programming, a program is built out of functions, in the maths sense: give one the same input and it always gives the same output, and it does nothing else.

The idea that makes this work is that a function is a first-class object. It can be treated like any other value:

• assigned to a variable
• stored in a list or a dictionary
• passed to another function as an argument
• returned from a function as a result

def double(x):
    return x * 2

fn = double                  # no brackets: the function itself, not a call to it
print(fn(5))                 # 10

operations = [double, abs, str]
for op in operations:
    print(op(-3))            # -6, then 3, then -3

Function types

A function takes values from one set, the domain, and gives back values from another, the codomain. The specification writes this as a function type:

Python can record this in the code itself, with type hints. They do not change how the program runs, but they state the function type:

def add(a: int, b: int) -> int:
    return a + b

print(add(2, 3))             # 5

Function application is simply the act of giving a function its argument: double(5) is the application of double to 5.

Higher order functions

A function is higher order if it takes a function as an argument, or returns one. It is what first class objects make possible.

def apply_twice(f, x):
    return f(f(x))

print(apply_twice(lambda n: n * 2, 3))                # 12
print(apply_twice(lambda s: s + "!", "hi"))            # hi!!

lambda makes a small anonymous function in one expression: lambda n: n * 2 is the function that takes n and returns n * 2. It is the same thing as a def, without a name.

Map, filter and reduce

Three higher order functions do nearly everything a loop over a list is used for. Each takes a function and a list.

from functools import reduce

numbers = [1, 2, 3, 4, 5, 6]

squares = list(map(lambda n: n * n, numbers))
evens = list(filter(lambda n: n % 2 == 0, numbers))
total = reduce(lambda a, b: a + b, numbers)

print(squares)               # [1, 4, 9, 16, 25, 36]
print(evens)                 # [2, 4, 6]
print(total)                 # 21
print(numbers)               # [1, 2, 3, 4, 5, 6], untouched

None of the three changes numbers. Each builds something new. That is deliberate, and it is the next section.

How reduce works

reduce carries a running result along the list. It starts with the first two items, then combines that with the third, and so on. Printing inside the function shows it:

from functools import reduce

def add_and_show(a, b):
    print(a, "+", b, "=", a + b)
    return a + b

print(reduce(add_and_show, [1, 2, 3, 4]))

Chaining them

The output of one is the input of the next, so they combine into a pipeline. The sum of the squares of the even numbers:

from functools import reduce

numbers = [1, 2, 3, 4, 5, 6]

evens = filter(lambda n: n % 2 == 0, numbers)
squares = map(lambda n: n * n, evens)
total = reduce(lambda a, b: a + b, squares)
print(total)                 # 56: 4 + 16 + 36

Python programmers often use a list comprehension for the same job. It is the same idea in a different spelling:

numbers = [1, 2, 3, 4, 5, 6]

print([n * n for n in numbers])                    # map
print([n for n in numbers if n % 2 == 0])          # filter
print(sum(n * n for n in numbers if n % 2 == 0))   # filter, map and reduce

Pure functions, immutability and lists

A function is pure if:

1. it always returns the same output for the same input, and
2. it has no side effects: it does not change anything outside itself, such as a global variable, a list it was given, a file or the screen.

def add_item_impure(basket, item):
    basket.append(item)          # changes the caller's own list: a side effect
    return basket

def add_item_pure(basket, item):
    return basket + [item]       # builds a new list and leaves the old one alone

original = ["milk"]
add_item_impure(original, "eggs")
print(original)                  # ['milk', 'eggs'], changed behind our back

original = ["milk"]
new_basket = add_item_pure(original, "eggs")
print(original, new_basket)      # ['milk'] ['milk', 'eggs']

A pure function has referential transparency: every call can be replaced by the value it returns, and the program means the same. square(4) can be swapped for 16 anywhere.

Why bother

The cost is that creating new values rather than changing old ones uses more memory and time.

Immutability

Functional programs prefer immutable data, which cannot change once created. In Python, tuples and strings are immutable:

# raises: TypeError
point = (3, 4)
point[0] = 9

You make a changed copy instead: point = (9,) + point[1:].

Lists as head and tail

In functional languages a list is built from the head, its first item, and the tail, the list of everything else. A list with nothing in it is the empty list, and cons builds a new list by putting an item on the front.

def head(items):
    return items[0]

def tail(items):
    return items[1:]

def cons(item, items):
    return [item] + items

def length(items):
    if items == []:
        return 0
    return 1 + length(tail(items))

def total(items):
    if items == []:
        return 0
    return head(items) + total(tail(items))

print(head([4, 5, 6]), tail([4, 5, 6]), cons(3, [4, 5, 6]))     # 4 [5, 6] [3, 4, 5, 6]
print(length([4, 5, 6]), total([4, 5, 6]))                      # 3 15

There is no loop and no variable that changes. The list is taken apart by recursion, which is how a language with no loops repeats anything.

Composition, partial application and closures

Composition

Composition joins two functions so that the output of one becomes the input of the next. Written in maths as f ∘ g, it means "apply g, then apply f".

def compose(f, g):
    return lambda x: f(g(x))

add_one = lambda x: x + 1
double = lambda x: x * 2

double_then_add = compose(add_one, double)     # first double, then add one
add_then_double = compose(double, add_one)     # first add one, then double

print(double_then_add(5))        # 11
print(add_then_double(5))        # 12

Notice that compose is itself a higher order function: it takes two functions and returns a new one. And the order matters. f ∘ g is generally not the same as g ∘ f.

Partial application

Partial application fixes some of a function's arguments and gives back a new function that waits for the rest.

from functools import partial

def power(base, exponent):
    return base ** exponent

square = partial(power, exponent=2)
cube = partial(power, exponent=3)

print(square(5), cube(2))        # 25 8

square is a function from one number to one number, made from a function of two numbers by supplying one of them in advance.

Closures and currying

A function written inside another can remember the variables of the function that made it, even after that function has finished. That is a closure.

def add(a):
    def inner(b):
        return a + b
    return inner

add5 = add(5)
print(add5(3))                   # 8
print(add(2)(10))                # 12

add5 has not been given a since it was created, but it still has it. add is a curried function: instead of taking two arguments at once, it takes one and returns a function that takes the other. add(2)(10) applies them one after the other.

A closure can hold changing state too, which is how a function with a memory is built without a class:

def make_counter():
    count = 0
    def counter():
        nonlocal count
        count += 1
        return count
    return counter

first = make_counter()
second = make_counter()
print(first(), first(), first(), second())     # 1 2 3 1

Each counter has its own count, hidden inside its closure where nothing else can reach it.

Summary of the paradigm

Key terms you must be able to define

First-class object

A value that can be assigned to a variable, stored in a data structure, passed as an argument and returned from a function. In functional languages, functions are first-class.

Higher-order function

A function that takes one or more functions as arguments, or returns a function as its result.

Map

A higher-order function that applies a function to every item of a list and returns the list of results.

Filter

A higher-order function that returns the items of a list for which a given function returns true.

Reduce

A higher-order function that combines all the items of a list into a single value by repeatedly applying a function.

Pure function

A function that always gives the same result for the same arguments and has no side effects.

Side effect

Any change a function makes outside itself, such as altering a global variable, its arguments, a file or the display.

Immutable

Describes data that cannot be changed once it has been created.

Composition

Combining two functions so that the output of one is the input of the other.

Partial application

Supplying some of a function's arguments to produce a new function that takes the remaining ones.

Closure

A function together with the variables of the surrounding scope that it can still use after that scope has ended.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Functional programming is a paradigm question: you are marked on defining each idea exactly and on using it.

• Define first-class, higher-order, pure and immutable separately and precisely, with an example of each
• Give the type of map, filter and reduce results: a list, a shorter list, and a single value
• Trace a pipeline stage by stage, writing down the intermediate list after each one
• Connect purity to benefits: testing, reasoning, parallel processing and caching
• Remember that composition order matters, and apply the right-most function first

Mistakes that cost marks here

from functools import reduce

nums = [3, 8, 1, 6]
result = reduce(lambda a, b: a + b,
                map(lambda n: n * 2,
                    filter(lambda n: n > 2, nums)))
print(result)

def make_multiplier(n):
    def multiply(x):
        return x * n
    return multiply

triple = make_multiplier(3)
print(triple(7))