Functional Programming in Python

Functional Programming : The Basics

Essentially, functional programming is a style of programming in which programs are written using mathematical functions that take immutable values as input and produce output expressions. The functional style of programming aims to avoid side-effects i.e. interactions with the world outside the function by means of, say, changing any state or depending on it. This independence makes it very easy to formally verify the “correctness” of a program.

See also:

https://en.wikipedia.org/wiki/Correctness_(computer_science)

In purely functional languages, the pure and impure parts of the program are kept separate(e.g. Haskell). By “impure”, I mean those parts of the program which can cause side-effects.

Python : Functional Style

We can write Python programs in functional style. However, since this language was not specifically tailored for functional programming, it would be needlessly complicated to program in a purely functional style.

In this article, I attempt to show how programs can be written in Python in a similar style to purely functional programming languages.

List Comprehension

The bread and butter of functional programming is the list. We often operate on lists, selecting elements from them or performing operations on each element.

Let us select all odd numbers from a list. In our usual procedural method, we would do something like this:

#!/usr/bin/env python

def filter_list(li):
    
    spam = []
    for i in li: 
        if i % 2 == 1:
            spam.append(i)

    return spam

print(filter_list([2, 4, 6, 7, 8, 1, 19, 200, 42, 31]))

We can accomplish the same thing with the code below.

li = [2, 4, 6, 7, 8, 1, 19, 200, 42, 31] 

nli = [x for x in li if x % 2 == 1]

print(nli)

In both cases, the output is as follows.

[7, 1, 19, 31]

Here, we have selected elements from a list by supplying a condition in the form of a boolean-valued function.

The second method is called a list comprehension. It is simply a way of generating lists from existing lists.

Here’s where iterators come in. An iterator is an object returned by an iterable object. We call next() on an iterator to get the next value in the sequence associated with it. Any object which implements the __iter__ method is said to be iterable. For instance, a list implements __iter__. Therefore, it is iterable and can be used in list comprehensions.

spam_iterator = iter("foobar")
ns = "".join([c.upper() for c in spam_iterator])
print(ns)

We patently obtain “FOOBAR”.

Generators

Now, while many native Python data structures are iterable, there is an easy method to generate iterators – generator functions. Observe:

def gen(MAX):
    
    i = 1 
    while i < MAX:
        yield i
        i += 1


i = gen(1000)

for j in range(12):
    print(i.next())

The above code will print out the integers 1 to 12.

We see that the gen function can be used to create an iterable object(a generator).

Alterantively, generators can be created by generator expressions, which are simply list comprehensions, but with the enclosing brackers replaced by parantheses.

g = (c.upper() for c in "foobar")

Thus, with the help of the general concept of iterability, we can implement some faux-functional features in python.

Map, Reduce, and Filter

map, reduce, and filter are functions that are integral to functional programming. These functions are provided by most functional langauges. Python implements these in its own way. map and filter can be seen as alternatives to list comprehensions.

map applies a function to all members of a sequence(an iterable). Observe:

def square:
    return x*x

foo = map(square, [1, 2, 3])
print(list(foo))

Output: [1, 4, 9]

Thus, map provides us the ability to apply a function to each member of a sequence, which is ubiquitous in functional programming.

In a similar vein, filter allows us to select certains items from a sequence.

def isUpper(c):
    return c == c.upper()

a = filter(isUpper, "FreedominObscureandoutlandishcOde")
print(list(a))

Output: ['F', 'O', 'O']

In this case, isUpper is the predicate. Only the values for which the predicate evaluates to true are kept.

Finally, reduce allows us to accumulate the application of a function to several values into one value. It is also known as fold. It is provided by the functools module.

from functools import reduce

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

print(reduce(add, list(range(1, 6))))

Output: 15

Anonymous Functions

We can create nameless functions(called lambda functions) for ease of use using the notation:

lambda <args> : <expr>

For instance, the filter example above could have been written as.

a = list(filter((lambda c: c == c.upper()), "FreedominObscureandoutlandishcOde"))

We trade readability for ease of use when using lambda functions.

References:

https://wiki.python.org/moin/Generators

https://docs.python.org/2/library/functools.html

https://wiki.haskell.org/List_comprehension