CMS 1

Functional Programming

# Terminology

• Data persistence
• Easiest way to store objects is using pickle
• Database - Organized collection of data
• Functional-style programming
• Programming paradigm focusing on the evaluation of mathematical functions
• Computations are 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
• Concepts of functional programming
• Support of first-class (higher-order) functions
• Functions are first-class citizens
• Anonymous Functions
• Recursion
• Closures - an abstraction binding a function to its scope
• ...
• PEP *
• Python Enhancement Proposals
• Primary documentation regarding the design and development of the Python programming language
• http://www.python.org/dev/peps/

# Writing Files

• Purpose
• Write the results of your computations to files
• Keep a log of errors
• Store intermediate results
• ...
• Works analog to reading files
• file.write(.)
• file.writelines(.)
• 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:
outfile.write("These numbers solve the world's problems!" + linesep)
for row in result:
for elem in row:
outfile.write(str(elem) + " ")
outfile.write(linesep)

• Appending is also possible
• 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:  # append
outfile.write("Now we really solve the world's problems!" + linesep)
for row in result:
for elem in row:
outfile.write(str(elem) + " ")
outfile.write(linesep)

• Storing objects is easiest with pickle
• Danger: not a human readable format
• # result needs to be defined before writing it
with open('test.dump', 'bw') as f:
pickle.dump(result, f)

• with open('test.dump', 'br') as f:


# Anonymous Functions

• Aka function constant, function literal, or lambda function
• Available in general purpose languages like Python and JavaScript
• Recently added to C++ (C++11)
• Function defined without being bound to an identifier
• Essential part of the functional programming paradigm
• Emphasizes the application of functions
• Prominent functional languages include Haskell and SML
• Used mainly in academia, but occasionally also in industrial projects
• Purpose and applications
• Arguments to a higher-order functions
• Special scoping rules
• Sorting, closures and currying
• Python Syntax
lambda arg [, arg2, ...]: expression

• Basic example
• f = lambda x, y: x + y
result = f(3, 4)

• Sorting a list of lists
• m = [[2, 'student', 'master'],
[3, 'student', 'bachelor'],
[1, 'works', 'full time']]
m.sort()

• Sorting a list of lists using a lambda function
• m = [[2, 'student', 'master'],
[3, 'student', 'bachelor'],
[1, 'works', 'full time']]
m.sort(key=lambda x: x[2])

• Sorting a list of strings
• #!/usr/bin/env python3

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


# Recursion

• Function calling itself
• Facilitates implementing certain algorithms
• It may be sufficient to consider the next step – not the whole problem at once
• Can express some mathematical concepts with straightforward, easy to read code
• A recursive implementation could be re-implemented with loops
• An implementation using loops instead of recursion tends 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 these data structures (eg. graph algorithms)
• ...
• Example: calculating the factorial of a non-negative integer
• $\mbox{factorial(n) = }\begin{cases}1 & \mbox{if n }\in \mbox{ set([0, 1])}\\ \mbox{n * factorial(n - 1)} & \mbox{otherwise} \end{cases}$
• Calculating a Factorial
• #!/usr/bin/env python3

def factorial(n):
"""
Return the factorial of n.
"""
assert n >= 0
if n <= 1:
return 1
return n * factorial(n - 1)

print(factorial(5))

• Example: calculating the nth Fibonacci number
• $\mbox{fib(n) = }\begin{cases}\mbox{n} & \mbox{if n }\in \mbox{ set([0, 1])}\\ \mbox{fib(n - 1) + fib(n - 2)} & \mbox{otherwise} \end{cases}$
• Fibonacci numbers
• def fib(n):
"""
Return the n-th fibonacci number (starting at 1).

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

print(fib(5))


# Map, Filter

• Examples of higher-order functions
• map(function, *iterables) - compute the function using arguments from the iterables
• For efficiency, map(.) returns an iterator
• Using map to calculate the squares of a sequence
• #!/usr/bin/env python3

squares = map(lambda x: x ** 2, [1, 2, 3, 4, 5])
print(list(squares))

• filter(function, iterable) - yield items of iterable for which function(item) is true
• Filtering even numbers
• #!/usr/bin/env python3

odd_numbers = filter(lambda x: x % 2, [1, 2, 3, 4, 5])
print(list(odd_numbers))


# Reduce, All and Any

• reduce(function, iterable[, initial]) - apply a function of two arguments cumulatively to the items of sequence
• Using reduce to 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)

• operator module provides functions for Python's operators
• E.g. operator.mul corresponds to lambda x, y: x * y
• all(iterable) -> bool
• returns True if bool(x) is True for all values in the iterable
• returns True if the iterable is empty
• any(iterable) -> bool
• returns True if bool(x) is True for any value in the iterable
• returns False if the iterable is empty

# Comprehensions

• List comprehension
• Particularly useful when doing a transformation on the entire list
• Less code to maintain than with a regular loop
• More verbose than using map and filter
• Comprehensions are also available for dictionaries and sets
• Applying list comprehensions
• #!/usr/bin/env python3

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

• Using dictionary comprehensions
• #!/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)

• Generator expressions
• Use parenthesis instead of square brackets
• Unlike list comprehensions, values are computed 'on demand'
• Simple generator expression
• #!/usr/bin/env python3

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


1. Read the first three chapters of the "Data Structures" wikibook: Introduction, Asymptotic Notation, Arrays
2. Do the 8th homework

# Summary

• Functional programming allows to directly express mathematical concepts
• Recursion tends to be easier to code but run slower than equivalent loops
• Anonymous functions facilitate sorting
• If you are interested in functional programming...
1. Get a designated textbook!
2. Learn a real functional programming language like Haskell.
• Topics not covered include