Functional Programming

Introduction to Software Engineering (CSSE 1001)

Write a function which disassembles a string into a list of characters comprising the string.

def disassemble(cs:str) -> list[str]:
    """Returns a list of characters comprising cs,
    maintaining order.
    >>> disassemble("")
    []
    >>> disassemble("abcdef")
    ['a', 'b', 'c', 'd', 'e', 'f']
    """

The old way…

def disassemble(xs: str) -> list[str]:
    ans = []
    for x in xs:
        ans.append(x)
    return ans

disassemble("abcdef") 
['a', 'b', 'c', 'd', 'e', 'f']

With list comprehension…

def disassemble(xs: str) -> list[str]:
    return [x for x in xs]

disassemble("abcdef") 
['a', 'b', 'c', 'd', 'e', 'f']

Lambda Functions (One line function definitions.)

Lambda Functions

One-line functions, like that of the previous slide, can be defined with lambda expressions which more closely resemble how mathematical functions, like: \(f(x) = x^2 + 1\), are denoted.

disassemble = lambda xs: [x for x in xs]

disassemble("abcdef")  
['a', 'b', 'c', 'd', 'e', 'f']

Lambda Functions

We may also apply the function without naming it which is why these lambda functions are sometimes called anonymous functions.

(lambda xs: [x for x in xs])("abcdef") 
['a', 'b', 'c', 'd', 'e', 'f']

Write a function which checks if a string has (strictly) more capitals than lower case letters, ignoring all other characters.

def more_capitals(cs:str) -> bool:
    """
    >>> more_capitals("aAbBcDd")
    False
    >>> more_capitals("CSSE 1001")
    True
    >>> more_capitals("")
    False
    """

A useful “hack”, remember that the integer value of True and False is zero and one.

True + True + False
2

more_capital = lambda cs: (sum(c.islower() for c in cs)
                > sum(c.isupper() for c in cs))

Write a lambda function to check if a positive integer is prime.

is_prime = lambda x: sum(not x%d for d in range(2, x)) == 0

List Comprehension Filtering

The elements of a list-comprehension may be filtered.

Example The numbers less than one hundred that are divisible both by three and seven.

[x for x in range(101) if not (x % 3) and not (x % 7)]
[0, 21, 42, 63, 84]

List Comprehension

The general pattern for a list comprehension is

[x for x in xs if P(x)]

where P(x) is some predicate P: xs -> bool

Iterator (Enumerable objects.)

Iterator

An iterator is a stream of countable objects that is possibly infinitely long.

Iterators are useful when you need the next member of some sequence. Or when you want to traverse a list, accessing elements exactly once.

List members are only calculated at the moment they are needed — this is called delayed computation.

Any object that is enumerable (i.e. elements are indexed) can be made iterable.

xs = iter([1, 2, 3]) 
next(xs)  
1
next(xs)  
2
next(xs)  
3
next(xs)  
StopIteration # An exception

xs = iter("bluey")  
next(xs)  
'b'

xs = iter({1: 'a', 2: 'b', 3: 'c'})  
next(xs)  
1  # iterates through keys 

Note: Python for-loops create an iterator object and invoked the next() method at each iteration.

Custom Iterators

In order for an object to admit an iterator it must implement the methods __iter__ and __next__.

The iterator method must return self.

class Foo():
     def __iter__(self):
        self.counter = 1
        return self  # obligatory

     def __next__(self):
        self.counter *= 2
        return self.counter

foo = Foo()
xs = iter(foo)  # iter wrapper must be applied 
next(xs) 
2
next(xs) 
4
next(xs) 
8  # will never exhaust
for x in xs: 
    print(x) 
2  # notice counter reset
4
8...  # infinite loop

We may instruct an iterator to exhaust itself by raising a StopIteration exception.

class Foo():
     def __iter__(self):
        self.counter = 1
        return self

     def __next__(self):
        self.counter *= 2
        if self.counter > 10:
             raise StopIteration
        return self.counter

Notice once we implement a stopping condition we can use a for loop without looping forever:

for x in xs:
    print(x)
2
4
8

Write a class that streams the prime numbers.

Higher-Order Function

Strictly speaking, a higher-order function is one that takes functions as input and returns a function as output.

In practice, higher order functions are those that take functions as input.

Map

A map is used to apply a function to every element of a list or iterable.

map(f, xs) <- [f(xs[0]), f(xs[1]), ..., f(xs[-1])]   
# not python code

map(f, xs) <- [f(x) for x in xs]
# not (but almost) python code

Notice the above will not work on infinite streams and does not delay computation.

The higher-order function: map returns an iterator.

div_by_three = lambda x: not x % 3 
# True when 3 divides x

xs = map(div_by_three, range(8))

xs 
<map object at 0x10d4c1b50> # an iterable

next(xs); next(xs); next(xs); next(xs) 
True; False; False; True

Forcing Evaluation

You can always force evaluate a finite stream by converting to a list:

list(map(div_by_three, range(8)) 
[True, False, False, True, False, False, True, False]

[x for x in map(div_by_three, range(8))] 
[True, False, False, True, False, False, True, False]

But this will only work when the stream eventually terminates.

Map: Alternative

Recall, an alternative to using map is to do a list comprehension. This will also force evaluation.

[div_by_three(x) for x in range(8)] 
[True, False, False, True, False, False, True, False]

Zip

A zip is used to combine two lists into a single list of tuples.

zip(xs, ys) <- [(xs[0], ys[0]), ..., (xs[n], ys[n])]
    where n = min(len(xs), len(ys))   # not python code
    
zip([1,2,3], [4,5,6,7]) <- [(1,4), (2,5), (3,6)]
# not python code

xs, ys = range(1, 4), range(4, 8)

zs = zip(xs, ys)
zs 
<zip object at 0x1034631c0> # an iterable

list(zs) 
[(1, 4), (2, 5), (3, 6)]

Write a function that given two lists performs the pointwise addition on them, truncating to the smaller list.

def list_add(xs: list[int], ys: list[int]) -> list[int]:
    """
    list_add([1, 2, 3], [4, 5, 6, 7])
    [5, 7, 9]
    """

lambda xs, ys: list(map(lambda zs: sum(zs), zip(xs, ys)))

Filter

A filter is used to remove/select elements from a list.

filter(p, xs) <- [x for x in xs if p(x)]
    where p is a predicate indicating what to KEEP
# not python code

filter(is_positive, [-1, 1, -2, 2 ,-3, 3])
[1, 2, 3]  # not python code

from random import randint
xs = [randint(-10,10) for _ in range(5)] 
# five random integers
xs 
[4, -5, -1, 2, -3]

zs = filter(lambda x: x>0, xs) 
zs 
<filter object at 0x103395340> # an iterable

list(zs) 
[4, 2]

All

all can be used to check if every member of a list satisfies some predicate — essentially ∀x; P(x).

all(xs) <- xs[0] and xs[1] and ... and xs[-1]
# not python code

all([True, True, True])
True

all([True, False, True])
False

# Are all elements of xs are positive?
xs = [1, 2, 3, 4]
all(map(lambda x: x>0, xs))  
True 

# Do all names start with 'B'?
names = ["Bluey", "Bingo", "Chilli", "Banjo"] 
all(map(lambda cs: cs[0]=='B', names)) 
False

any can be used to check if there is a member of a list satisfies some predicate — essentially ∃x; P(x).

any(xs) <- xs[0] or xs[1] or ... or xs[-1]
# not python code

any([True, True, True])
True

any([True, False, True])
True

any([False, False])
False

# Is any element of xs negative?
xs = [1, 2, 3, 4] 
any(map(lambda x: x<0, xs))  
False 

# Does any name start with 'C'?
names = ["Bluey", "Bingo", "Chilli", "Banjo"] 
any(map(lambda cs: cs[0]=='C', names)) 
True

Give a single line definition for all and any using filter. Your solution only has to work on lists (not streams).

Folds

Folding

Folding is the process of repeatedly applying a bivariate function to a sequence of values.

For example, folding addition over xs = [1,2,3] would result in \[ 1 + 2 + 3 \] using infix notation or \[ +(+(1,2), 3) \] using prefix notation.

Reduce

reduce(f, xs) folds the bivariate function f over the list xs.

reduce(f, xs) <- f(...f(f(xs[0], xs[1]), xs[2]), ..., xs[-1])
# not python

reduce(@, xs) <- xs[0] @ xs[1] @ ... @ xs[-1]
    where @ is some infix function
# not python

from functools import reduce
xs = [2, 3, 4]
reduce(lambda x,y: x+y, xs) 
9
reduce(lambda x,y: x*y, xs) 
24
reduce(lambda x,y: x**y, xs) 
4096 
(2**3)**4  # left associative 
4096
2**(3**4)  # right associative 
2417851639229258349412352 

What should reduce do on empty or singleton lists?

That depends on the function being folded and thereby this value needs to be an input to reduce.

Usually (but not always) it is whatever the zero or identity of the input function. This is what it needs to be for the recursion to work.

xs = [2] 

reduce(lambda x,y: x+y, xs, 0)  
2

reduce(lambda x,y: x*y, xs, 1)  
2

reduce(lambda x,y: x**y, xs, 1)  
2

xs = []

reduce(lambda x,y: x+y, xs, 0)  
0

reduce(lambda x,y: x*y, xs, 1)  
1

reduce(lambda x,y: x**y, xs, 1)  
1

Of course, we can select any base case we choose. Presuming the types are compatible.

reduce(lambda x,y: x+y, [1,2,3], 10)  
16

reduce(lambda x,y: x*y, [1,2,3], 0)   
0

reduce(lambda x,y: x+y, [[1], [2], [3]], [0])   
[0,1,2,3]  # notice the side 0 was added

Define sum, prod of integer lists using reduce.

Define concatenate which, given a list of lists, returns the concatenation of those lists using reduce.

Define all using reduce.

Define length using fold.

Next

Recursion.