Programming languages support decomposing problems in several different ways:
Most programming languages are procedural: programs are lists of instructions that tell the computer what to do with the program’s input.
In declarative languages, you write a specification that describes the problem to be solved, and the language implementation figures out how to perform the computation efficiently.
Object-oriented programs manipulate collections of objects. Objects have internal state and support methods that query or modify this internal state in some way.
Functional programming decomposes a problem into a set of functions. Ideally, functions only take inputs and produce outputs, and don’t have any internal state that affects the output produced for a given input.
In a functional program, input flows through a set of functions. Each function operates on its input and produces some output.
Functional style discourages functions with side effects that modify internal state or make other changes that aren’t visible in its return value. Functions that have no side effects at all are called purely functional.
Avoiding side effects means not using data structures that get updated as a program runs; every function’s output must only depend on its input.
Recursion is used as a primary control structure.
There is a focus on list processing. Lists are often used with recursion on sublists as a substitute for loops.
Functional programming worries about what is to be computed rather than how it is to be computed.
Much functional programming utilizes “higher order” functions (in other words, functions that operate on functions that operate on functions).
iterator
An iterator is an object representing a stream of data; this object returns the data one element at a time.
A Python iterator must support a method called __next__() that takes no arguments and always returns the next element of the stream.
If there are no more elements in the stream, __next__() must raise the StopIteration exception.
L = [1,2,3]
it = iter(L)
print(it, type(it))
print(it.__next__()) # same as next(it)
print(next(it))
print(next(it))
print(next(it))
Python expects iterable objects in several different contexts, the most important being the for statement.
In the statement for X in Y, Y must be an iterator or some object for which iter() can create an iterator.
These two statements are equivalent:
for i in iter(obj):
print(i)
for i in obj:
print(i)
Iterators can be materialized as lists or tuples:
L = [1,2,3]
iterator = iter(L)
t = tuple(iterator)
print(t)
Sequence unpacking also supports iterators:
L = [1,2,3]
iterator = iter(L)
a,b,c = iterator
a,b,c
Any Python sequence type, such as strings, will automatically support creation of an iterator.
m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4,
'May': 5, 'Jun': 6, 'Jul': 7, 'Aug': 8,
'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12}
for key in m:
print(key, m[key])
L = [('Italy', 'Rome'), ('France', 'Paris'),
('US', 'Washington DC')]
print(dict(iter(L)) == dict(L))
S = {2, 3, 5, 7, 11, 13}
for i in S:
print(i)
Two common operations on an iterator’s output are
1) performing some operation for every element,
2) selecting a subset of elements that meet some condition.
For example, given a list of strings, you might want to strip off trailing whitespace from each line:
line_list = [' line 1\n', 'line 2 \n', '']
# List comprehension -- returns list
stripped_list = [line.strip() for line in line_list]
print(stripped_list)
stripped_list = [line.strip() for line in line_list
if line != ""]
print(stripped_list)
seq1 = 'abc'
seq2 = (1,2,3)
[(x, y) for x in seq1 for y in seq2]
map(f, iterA, iterB, ...) returns an iterator over the sequence
f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ....
def upper(s):
return s.upper()
list(map(upper, ['sentence', 'fragment']))
You can of course achieve the same effect with a list comprehension.
[upper(s) for s in ['sentence', 'fragment']]
filter(predicate, iter) returns an iterator over all the sequence elements that meet a certain condition, and is similarly duplicated by list comprehensions.
A predicate is a function that returns the truth value of some condition; for use with filter(), the predicate must take a single value.
def is_even(x):
return (x % 2) == 0
list(filter(is_even, range(10)))
This can also be written as a list comprehension:
[x for x in range(10) if is_even(x)]
for x in filter(is_even, range(10)):
print(x)
sorted(iterable, key=None, reverse=False) collects all the elements of the iterable into a list, sorts the list, and returns the sorted result.
The key and reverse arguments are passed through to the constructed list’s sort() method.
import random
# Generate 8 random numbers between [0, 10000)
rand_list = random.sample(range(10000), 8)
print(rand_list)
print(sorted(rand_list))
print(sorted(rand_list, reverse=True))
zip(iterA, iterB, ...) takes one element from each iterable and returns them in a tuple:
list(zip(['a', 'b', 'c'], [1, 2, 3]))
all and zip¶The any(iter) and all(iter) built-ins look at the truth values of an iterable’s contents.
any() returns True if any element in the iterable is a true value, and all() returns True if all of the elements are true values:
print(any([0,1,0]))
print(any([0,0,0]))
print(any([1,1,1]))
print(all([0,1,0]))
print(all([0,0,0]))
print(all([1,1,1]))
The itertools module contains a number of commonly-used iterators as well as functions for combining several iterators.
count, repeat, cycle, chain
itertools.count(n) returns an infinite stream of integers, increasing by 1 each time.
import itertools
import random
rand = random.randint(0,10000)
cnt = 0
for f in itertools.count() :
cnt +=1
if f == rand:
break
print('guess {} times'.format(cnt))
combinations
The itertools.combinations(iterable, r) returns an iterator giving all possible r-tuple combinations of the elements contained in iterable.
itertools.permutations(iterable, r=None) returning all possible arrangements of length r:
list(itertools.combinations([1, 2, 3, 4, 5], 2))
list(itertools.permutations([1, 2, 3, 4, 5], 2))
# Another eight queens problem solution
from itertools import permutations
SIZE = 8
cols = range(SIZE)
for vec in permutations(cols):
if (SIZE == len(set(vec[i]+i for i in cols))
== len(set(vec[i]-i for i in cols))):
print(vec)
The functools module contains some higher-order functions.
A higher-order function takes one or more functions as input and returns a new function.
functools.partial
For programs written in a functional style, you’ll sometimes want to construct variants of existing functions that have some of the parameters filled in.
Consider a Python function f(a, b, c); you may wish to create a new function g(b, c) that’s equivalent to f(1, b, c); you’re filling in a value for one of f()‘s parameters. This is called “partial function application”.
import functools
def log(message, subsystem):
"""Write the contents of 'message' to the specified subsystem."""
print('%s: %s' % (subsystem, message))
pass
server_log = functools.partial(log, subsystem='server')
server_log('Unable to open socket')
functools.reduce
functools.reduce(func, iter, [initial_value]) cumulatively performs an operation on all the iterable’s elements and, therefore, can’t be applied to infinite iterables.
func must be a function that takes two elements and returns a single value.
functools.reduce() takes the first two elements A and B returned by the iterator and calculates func(A, B). It then requests the third element, C, calculates func(func(A, B), C), combines this result with the fourth element returned, and continues until the iterable is exhausted.
If the iterable returns no values at all, a TypeError exception is raised. If the initial value is supplied, it’s used as a starting point and func(initial_value, A) is the first calculation.
import operator, functools
functools.reduce(operator.concat, ['A', 'BB', 'C'])
import operator, functools
functools.reduce(operator.mul, [1,2,3])
import operator, functools
functools.reduce(operator.add, [1,2,3,4])
When writing functional-style programs, you’ll often need little functions that act as predicates or that combine elements in some way.
If there’s a Python built-in or a module function that’s suitable, you don’t need to define a new function.
If the function you need doesn’t exist, you need to write it.
One way to write small functions is to use the lambda statement.
lambda takes a number of parameters and an expression combining these parameters, and creates an anonymous function that returns the value of the expression
adder = lambda x, y: x+y
adder(1,2)
import functools
functools.reduce(lambda x,y:x*y, [1,2,3])
import functools
functools.reduce(lambda x,y:x+y, [1,2,3,4])
list(map(lambda x: x.upper(),
['sentence', 'fragment']))
list(filter(lambda x: x%2 == 0, range(10)))
from functools import reduce
def factorial(n):
return reduce(lambda x,y: x*y, range(1, n+1))
factorial(100)
score = {'A':20,'B':15, 'C':60, 'D':40}
sorted(score.items(), key=lambda kv:kv[1])
Exercise
l = [28,14,'28', 5,'9', '1', 0, 6, '23',19]
l = [28,14,'28', 5,'9', '1', 0, 6, '23',19]
print(sorted(l, key=int))
l = [28,14,'28', 5,'9', '1', 0, 6, '23',19]
print(sorted(l, key=str))
def reduce(function, iterable, initializer=None)
def reduce(function, iterable, initializer=None):
it = iter(iterable)
if initializer is None:
value = next(it)
else:
value = initializer
for element in it:
value = function(value, element)
return value
reduce(lambda x,y:x+y, [1,2,3])