Functional-Style Programming

• Programming paradigm focusing on evaluating mathematical functions
• Based on combining functions that don't modify their arguments
• Functions don't use or change the program's state
• Allows directly expressing mathematical concepts
• Functions solely use return values to communicate their results
• In theory, functions are completely independent of each other
• Prominent functional languages include Elixir, Erlang, Haskell and SML
• Used mainly in academia, but also in industrial projects

Concepts of functional programming

Pure functions

First-class and higher-order functions

Functions are first-class citizens

Anonymous (lambda) functions

Recursion

Function definition depends on (a simpler version of) itself

Closures

an abstraction binding a function to its scope
a closure is a record storing a function together with an environment

Currying

Partially applying arguments to a function

...

Purpose

• Write the results of your computations to files
• Keep a log of errors
• Store intermediate results
• ...

Works analog to reading files

with open(filename, 'w', encoding='utf8') as f:
    f.write(.)
    f.writelines(.)

with open(filename, 'w', encoding='utf8') as f:
    print(., file=f)

Example

from os import linesep
# ... long computation
result = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
with open('result.txt', 'w', encoding='utf-8') as outfile:  # w => write
    outfile.write("These numbers solve the world's problems!" + linesep)
    for row in result:
        for elem in row:
            outfile.write(str(elem) + ' ')
        print(file=outfile)

Example: Append

Writing to the end of an existing file

from os import linesep
# ... long computation
result = [[1, 3, 2],
          [4, 5, 6],
          [9, 8, 7]]
with open('result.txt', 'a', encoding='utf-8') as outfile:  # a => append
    outfile.write("Now we really solve the world's problems!" + linesep)
    for row in result:
        for elem in row:
            print(str(elem), file=outfile, end=' ')
        outfile.write(linesep)

Example: Writing Binary Files

Danger: binary files are not human readable

Storing objects is easiest with pickle

import pickle
result = [[1, 3, 2],
          [4, 5, 6],
          [9, 8, 7]]
with open('test.dump', 'wb') as f:  # wb or bw => write binary
    pickle.dump(result, f)

import pickle
with open('test.dump', 'rb') as f:  # rb or br => read binary
    result = pickle.load(f)

Aka function constant, function literal, or lambda function

• Function defined without being bound to an identifier
• Essential part of the functional programming paradigm
• Emphasizes the application of functions

Purpose and Applications

• Arguments to a higher-order functions
• Special scoping rules
• Sorting, callbacks, closures, ...

lambda arg [, arg2, ...]: expression

Example: Assign Lambda to Identifier

It is possible to assign lambdas to identifiers

func = lambda x, y: x + y
result = func(3, 4)

Visualize execution

Example: Sorting a List of Lists

Default sorting criterion: each sublist's first element

m = [[2, 'student', 'master'],
     [3, 'student', 'bachelor'],
     [1, 'works', 'full time']]
m.sort()

Visualize execution

m = [[2, 'student', 'master'],
     [3, 'student', 'bachelor'],
     [1, 'works', 'full time']]
m.sort(key=lambda x: x[2])

Example: Sorting a List of Strings

By default, strings are sorted by the unicode code points of their characters

Using lambdas allows more natural sorting

#!/usr/bin/env python3

names = ['betty', 'Anna', 'Sue', 'gernot', 'Luis', 'Therese', 'amelie', ]
names.sort()  # likely not what we'd expect
names.sort(key=lambda x: x.lower())

Visualize execution

Function calling itself

• The definition of a function depends on a simpler version of itself
• Facilitates implementing certain algorithms
• Allows focusing on the next step - not the whole problem at once
• Mathematical concepts can be expressed with straightforward, easy to read code
  • Recursive implementation can be re-implemented with loops
  • Loops tend to be more efficient but harder to code
  • Watch out for the limit on the depth of recursion (avoid stack overflows)

Applications

• Low level: working with data structures such as lists and trees
• High level: algorithms using such data structures (eg. graph algorithms)
• Divide and conquer serves as top-down approach to problem solving
• Implementation of solutions to certain mathematical problems
• ...

Example: Factorial of a Non-negative Integer

$\text{factorial(n) = }\{\begin{array}{ll}1& \text{if n }\in \text{ set([0, 1])}\\ \text{n * factorial(n - 1)}& \text{otherwise}\end{array}$

#!/usr/bin/env python3

def factorial(n):
    """
    Return the factorial of n.
    """
    assert n >= 0
    if n <= 1:  # base case
        return 1
    return n * factorial(n - 1)  # recursion: use solution to smaller problem

print(factorial(5))

Example: Calculate the n^th Fibonacci number

$\text{fib(n) = }\{\begin{array}{ll}\text{n}& \text{if n }\in \text{ set([0, 1])}\\ \text{fib(n - 1) + fib(n - 2)}& \text{otherwise}\end{array}$

def fib(n):
    """
    Return the n-th fibonacci number (starting at 1).

    Note: this is an inefficient implementation.
    """
    if n <= 1:  # base case
        return n
    return fib(n - 1) + fib(n - 2)  # recursive case

print(fib(5))

map, filter

Examples of higher-order functions

For efficiency, both return iterators yielding values one at a time

map(function, *iterables)

compute the function using arguments from the iterables

filter(function, iterable)

yield items of iterable for which function(item) is true

Example: map

Calculate the squares of a sequence

#!/usr/bin/env python3

squares = map(lambda x: x ** 2, [1, 2, 3, 4, 5])
print(squares)  # nothing was computed yet
print(list(squares))

Visualize execution

Example: filter

Filter odd numbers

#!/usr/bin/env python3

odd_numbers = filter(lambda x: x % 2, [1, 2, 3, 4, 5])
print(odd_numbers)  # nothing was computed yet
print(list(odd_numbers))

Visualize execution

Reduce, All, Any

functools.reduce(function, iterable[, initial])

apply a function with two arguments cumulatively to iterable

all(iterable) -> bool

return True if bool(x) is True for all values in the iterable

return True if the iterable is empty

input can be created with map using a boolean valued function

any(iterable) -> bool

return True if bool(x) is True for any value in the iterable

return False if the iterable is empty

Example: Calculate the Product of a Sequence

#!/usr/bin/env python3

import functools
product = functools.reduce(lambda x, y: x * y, [1, 2, 3, 4, 5])
print(product)

Visualize execution

#!/usr/bin/env python3

import functools
from operator import mul
product = functools.reduce(mul, [1, 2, 3, 4, 5])
print(product)

Example: Are There Only Odd Numbers?

numbers = [1, 3, 17]
if all(map(lambda x: x % 2, numbers)):
    print('only odd numbers')
numbers.append(2)
if not all(map(lambda x: x % 2, numbers)):
    print('not just odd numbers')

Visualize execution

Example: Did All Students pass?

from collections import namedtuple

class Result:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade

results = [Result('Joe', 3), Result('Maggie', 2), Result('Josh', 1),
           Result('Sue', 2)]
if not any(map(lambda r: r.grade == 5, results)):
    print('All students passed.')
results.append(Result('Francis', 5))
if any(map(lambda r: r.grade == 5, results)):
    print('At least one student failed.')

Visualize execution

Comprehensions

• Particularly useful when doing a transformation on entire collections
• Less code to maintain than with a regular loop
• More verbose than using map and filter
• Comprehensions are available for lists, dictionaries and sets
• Generator expressions use lazy evaluation and are more memory efficient

Example: List Comprehension

#!/usr/bin/env python3

squares = [x ** 2 for x in [1, 2, 3, 4, 5]]  # ~map
print(squares)
odd_numbers = [x for x in [1, 2, 3, 4, 5] if x % 2]  # ~filter
print(odd_numbers)

Visualize execution

Example: Dictionary Comprehension

#!/usr/bin/env python3

"""
Simple dict comprehension exchanging the keys and values of a dict.

Assumes that the values are unique and hashable.
"""

d = {'Martin': 7, 'Sue': 5, 'Pat': 12, 'Chris': 4}
print(d)
d = {v: k for k, v in d.items()}
print(d)

Visualize execution

Example: Generator Expression

Use parenthesis instead of square brackets

Unlike list comprehensions, values are computed 'on demand'

#!/usr/bin/env python3

squares = (x ** 2 for x in [1, 2, 3, 4, 5])
print(squares)
print(list(squares))

Visualize execution