Python - Functional Programming

Different programming languages take different approach towards programming. These approaches are also called programming paradigms. Imperative, object oriented, declarative and functional paradigms are widely adapted. Python is a multi-paradigm language. It supports imperative, object oriented, as well as functional programming approach.

Functional programming paradigm recommends dividing the programming logic into set of functions that only take input and produce output not that affects the output produced for a given input. 

In this chapter we discuss certain features of Python which help in writing functional-style programs.

Lambda function

The def keyword is used to define a named function. Lambda keyword is used to create anonymous function. Usually such a function is created on the fly and meant for one-time use. The general syntax of lambda is as follows:

lambda arg1, arg2… : expression

A lambda function can have any number of arguments but there’s always a single expression after : symbol. The value of expression becomes return value of lambda function. For example

>>> add=lambda a,b:a+b

An anonymous function is declared with lambda keyword that receives a and b and returns a+b.. The anonymous function object is assigned to identifier called add. We can now use it as a regular function call

>>> print (add(2,3
5

Note that the above lambda function is equivalent to a normal function declared using def keyword as below:

>>> def add(a,b);
return a+b
>>> print (add(2,3))
5

However, body of lambda function can have only one expression. Therefore it can substitute a normal function having complex logic involving conditionals, loops etc.

In Python, function is a called a first order object, because function can also be used as argument, just as number, string, list etc. A lambda function is often used as argument function to functional programming tools such as map(), filter() and reduce() functions.

Recursion:

A function can call any other function, including itself also. Function is said to be recursive if it calls itself. Recursion is used when a process is defined in terms of itself. Obviously, a recursive call by function to itself causes an infinite loop. Hence recursive call is always conditional. Recursive approach provides a very concise solution to complex problem having many iterations.

In general, any iterative process can be expressed in the form of recursion. It takes a bit of expertise to write recursive equivalent of classical loop. The most popular example of recursion is calculation of factorial. A layman's definition of factorial of a number is multiplication of all numbers from 1 to itself. However, in mathematics factorial is defined as:

n! = n X (n-1)!

Here we have used factorial itself to define factorial. Such problems are ideally suited to be expressed recursively.

We can perform this calculation using a loop as per following code:

>>> def factorial(x):
f=1
for i in range(1, x+1):
f=f*i
return f


>>> factorial(5)
120

Now we shall try to write recursive equivalent of above loop. Look at mathematical definition of factorial once again.

n!=nX(n-1)!

Substitute n with 5. The expression becomes

5!=5X4! = 5X4X3! = 5X4X3X2! = 5X4X3X2X1! = 5X4X3X2X1 = 120

Let us see graphically the step by step process of computing factorial value of 5.

Above process involves successively performing factorial calculation of number by decrementing the number till it reaches 1. Following is recursive function to calculate factorial

>>> def factorial(n):    
   if n == 1:
       print (n)
       return 1    
   else:
       print (n,'*', end=' ')
       return n * factorial(n-1)
>>> factorial(5)
5 * 4 * 3 * 2 * 1
120

First time, the factorial function is called with 5 as argument. The function recursively calls itself, with reducing value. Functions return to their earlier call after the number reaches 1. Return value of first call is cumulative product of return values of all calls.

Iterator

Python uses iterators are implicitly while working with collection data types such as list, tuple or string. That's why these data types are quite  called iterables.

We normally use for loop to iterate through an iterable as follows:

for element in  sequence:

     print (element)

An iterator an object represents a data stream that returns one element at a time. It follows iterator protocol which requires it to support  __iter__() and __next__() methods. Python’s built-in method iter() implements __iter__() method. It receives an iterable and returns iterator object.

>>> iter("aa")
<str_iterator object at 0x05A73190>
>>> iter([1,2,3])
<list_iterator object at 0x05CE5E30>
>>> iter((1,2,3))
<tuple_iterator object at 0x05CE5E50>
>>> iter({})
<dict_keyiterator object at 0x05CDD480>
>>> iter(100)
Traceback (most recent call last):
 File "<pyshell#7>", line 1, in <module>
   iter(100)
TypeError: 'int' object is not iterable

Note that if the argument is not iterable, TypeError is encountered.

Iterator object has __next__() method. Every time it is called, it returns next element in iterator stream. When the stream gets exhausted, StopIteration error is raised.

>>> string="computer"
>>> it=iter(string)
>>> it.__next__()
'c'
>>> it.__next__()
'o'
>>> it.__next__()
'm'
>>> it.__next__()
'p'
>>> next(it)
'u'
>>> next(it)
't'
>>> next(it)
'e'
>>> it.__next__()
'r'
>>> it.__next__()
Traceback (most recent call last):
 File "<pyshell#10>", line 1, in <module>
   it.__next__()
StopIteration

The built-in function next() internally calls __next__() method on iterator object. Hence it.__next__()

is equivalent to next(it).

A for loop over any iterable object, actually implements iterator protocol internally as  per the following process:

>>> string="computer"
>>> it=iter(string)
>>> while True:
try:
char=next(it)
print (char)
except StopIteration:
break

This is equivalent to using a for loop as below:

>>> for char in 'computer':
print (char)

The 'try' and 'except' keywords are used in exception handling, which will be discussed in a subsequent chapter.

Generator

A generator is a special type of function. Even though it looks like a normal function , it doesn’t return a single value. It returns an iterator object returning stream of values. In a generator function yield statement is used rather than return statement found in a normal function.

The generator is called just like a normal function. It pauses on encountering yield keyword. The yielded value is returned to calling environment. However, local variables and their states are saved internally. Function resumes when __next__() method of iterator is called. The function finally terminates when __next__() or next() raises StopIteration.

In following example function generator() acts as a generator. It yields one character at a time from the string sequence successively on every call of next()

def generator(x):
       for i in x:
               print ("yielding", i)
               yield i
gen=generator('Hello')
while True:
       try:
               print ("received ",next(gen))
               print ("next character")
       except StopIteration:
               print ("end of generator")
               break

Output:

yielding H
received  H
next character
yielding e
received  e
next character
yielding l
received  l
next character
yielding l
received  l
next character
yielding o
received  o
next character
end of generator

We can use for statement to traverse elements over generator. In this case next() function is called implicitly and StopIteration is also automatically taken care of.

def generator(x):
       for i in x:
               print ("yielding",i)
               yield i
gen=generator("hello")
for char in gen:
       print ("received ",char)
       print ("next character")
print ("end of generator")

In case of generator elements are generated dynamically. Since next item is generated only after first is consumed, it is more memory efficient than iterator.

List comprehension

List comprehension techniques follow mathematical set builder notation. It is a very concise and efficient mechanism of creating new list by performing a certain process on each item of existing list. List comprehension is considerably efficient than processing a list by for loop.

Suppose we want to compute square of each number in a list and store squares in another list object. We can do it by a for loop as shown below:

squares=[]
for num in range(6):
        squares.append(pow(num,2))
print (squares)

The squares list object is displayed as follows:

[0, 1, 4, 9, 16, 25]

List comprehension technique easily achieves same result more efficiently. List comprehension statement uses following syntax:

newlist = [x for x in sequence]

We use above format to construct list of squares using list comprehension.

>>> squares=[x*x for x in range(6)]
>>> squares
[0, 1, 4, 9, 16, 25]

We can even generate a dictionary or tuple object as a result of list comprehension.

>>> [{x:x*10} for x in range(1,6)]
[{1: 10}, {2: 20}, {3: 30}, {4: 40}, {5: 50}]

Nested loops can also be used in a list comprehension expression. To obtain list of all combinations of items from two lists:

>>> [{x:y} for x in range(1,3) for y in range(100,300,100)]
[{1: 100}, {1: 200}, {2: 100}, {2: 200}]

The resulting list stores all combinations of one number from each list

We can even have if condition in list comprehension. Following statement will result in list of all non-vowel alphabets in a string.

>>> consonants=[char for char in "Beautiful" if char not in ['a','e','i','o','u']]
>>> consonants
['B', 't', 'f', 'l']

The itertools module

The module of Python’s standard library consists of more efficient and fast iteration tools.

map() function

Thebuilt-in  map() function is especially useful where it is required to process each item from one or more iterable sequences (string, list, tuple or dictionary). It subjects each element in the iterable to another function which may be either a built-in function, a lambda function or a user-defined function and returns the mapped object. The map() function needs two arguments:

map(Function, Sequence(s))

In following example we first define a function to compute factorial of a number.

def factorial(n):    
    if n == 1:
        return 1    
    else:
        return n * factorial(n-1)

The map() function applies it to each element in the numbers[] list. The map object is converted to generate squares[] list.

numbers=[1,2,3,4,5]
factmap=map(factorial,numbers)
print (list(factmap))

Output:

[1,2,6,24,120]

Instead of user-defined function, we now use factorial() function from math module and use it as argument to map() function.

from math import factorial
numbers=[1,2,3,4,5]
factmap=map(factorial,numbers)
print (list(factmap))

Next example uses a lambda function as argument to map() function. The lambda function itself takes two arguments taken from two lists and returns first number raised to second.The resulting mapped object is then parsed to output list.

powersmap=map(lambda x,y: x**y, [10,20,30], [4,3,2])
print (list(powersmap))

Output:

[10000, 8000, 900]

filter() function

The filter() function also receives two arguments, a function with Boolean return value and a sequence. Only the items for which the function returns True are stored in a filter object.

In following example, a function isvowel() is defined which returns True if the character is a not a vowel (a, e,i or u), otherwise returns False. This function is used inside filter() along with a string containing few lines from 'zen of Python'. Vowels from the lines are filtered out and only consonants are returned.

def isvowel(x):
       for char in x:
               if char in ['a','e','i','o','u']:
                       return False
       else:
               return True
string='''
Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
'''
consonants=list(filter(isvowel,string))
print (''.join(consonants))

Output:

Btfl s bttr thn gly.
Explct s bttr thn mplct.
Smpl s bttr thn cmplx.
Cmplx s bttr thn cmplctd.
Flt s bttr thn nstd.

Lambda function can also be used as a filter. Following program use lambda function that filters all vowels from given string.

string='''
Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
'''
consonants=list(filter(lambda x: x not in ['a','e','i','o','u'],string))
print (''.join(consonants))

reduce() function

Unlike map and filter functions, reduce() is not a built-in function, but is defined in built-in functools module. It also needs two arguments, a function and an iterable. However it returns a single value. The argument function is applied to two successive items in the list from left to right. Result of the function in first call becomes first argument and third item in list becomes second. Cumulative result is the return value of reduce() function.

In the example below, add() function is defined to return addition of two numbers. This function is used in reduce() function along with a range of numbers between 0 to 100. Output is sum of first 100 numbers.

import functools
def add(x,y):
        return x+y

num=functools.reduce(add, range(101))
print ('sum of first 100 numbers ',num)

Output:

sum of first 100 numbers  5050

We can use a lambda function instead of user-defined add() function for the same output.

num=functools.reduce(lambda x,y:x+y, range(101))

The functool module of Python's standard library consists of more first order functions which act on or return other function.