>>> def square(x):
...     return x *x
... 
>>> square(4)
16

Functions can be assigned like any other objects.

>>> f = square
>>> f(4)
16

They can be passed as arguments to other functions.

>>> def fsum(f, x, y):
...     return f(x) + f(y)
... 
>>> fsum(square, 3, 4)
25

Anonymous functions can be created using the lambda operator.

>>> fsum(lambda x: x*x, 3, 4)
25

Functions can even return new functions. We'll see that later.

Python has built-in support for lists.

>>> [1, 2, 3, 4]
[1, 2, 3, 4]
>>> ["hello", "world"]
["hello", "world"]
>>> [0, 1.5, "hello"]
[0, 1.5, "hello"]

A List can contain another list as member.

>>> a = [1, 2]
>>> b = [1.5, 2, a]
>>> b
[1.5, 2, [1, 2]]

A list can contain even it self.

>>> a = [1, 2]
>>> a.append(a)
>>> a
[1, 2, [...]]

Some operations on lists.

>>> x = [5, 2, 3, 1]
>>> len(x)
5
>>> 2 in x
True
>>> 4 in x
False
>>> x.sort()
>>> x
[1, 2, 3, 5]

The sorted function returns a new sorted list instead of modifying the original.

>>> x = [5, 2, 3, 1]
>>> sorted(x)
[1, 2, 3, 5]

The sorted function and sort method can take a key function as argument.

>>> x = ["a", "c", "D", "B"]
>>> sorted(x)
['B', 'D', 'a', 'c']
>>> sorted(x, key=lambda a: a.lower())
['a', 'B', 'c', 'D']

Dictionaries are like lists, but they can be indexed with non integer keys also. Unlike lists, dictionaries are not ordered.

>>> a = {'x': 1, 'y': 2, 'z': 3}
>>> a['x']
1
>>> a['z']
3
>>> a['zz']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'zz'
>>> a.get('zz', 0)
0

The in operator can be used to check if a key is present in the dictionary.

>>> 'z' in a
True
>>> 'zz' in a
False

The del operator can be used to delete an item from a dictionary.

>>> del a['x']
>>> a
{'y': 2, 'z': 3}
>>> 'x' in a
False

Compute frequency of words in a given file.

Lets start with a function to count frequency of words, given a list of words.

def word_frequency(words):
    """Returns frequency of each word given a list of words.

        >>> word_frequency(['a', 'b', 'a'])
        {'a': 2, 'b': 1}
    """
    frequency = {}
    for w in words:
        frequency[w] = frequency.get(w, 0) + 1
    return frequency

Getting words from a file is very easy.

def read_words(filename):
    return open(filename).read().split()

We can combine these two functions to find frequency of all words in a file.

def main(filename):
    words = read_words(filename)
    frequency = word_frequency(words)
    for word, count in frequency.items():
        print word, count

if __name__ == "__main__":
    import sys
    main(sys.argv[1])

• Write a program to count frequency of characters in a given file.

• Write a function invertdict to interchange keys and values in a dictionary. For simplicity, assume that all values are unique.

  >>> invertdict({'x': 1, 'y': 2, 'z': 3})
  {1: 'x', 2: 'y', 3: 'z'}
  

• Write a program to find anagrams in a given list of words. Two words are called anagrams if one word can be formed by rearranging letters of another. For example "eat", "ate" and "tea" are anagrams.

  >>> anagrams(['eat', 'ate', 'done', 'tea', 'soup', 'node'])
  [['eat', 'ate', 'tea], ['done', 'node'], ['soup']]
  

List Comprehensions provide a concise way of creating lists.

Here are some simple examples for transforming a list.

>>> a = range(10)
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> [x for x in a]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> [x*x for x in a]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

It is also possible to filter a list using if condition inside a list comprehension.

>>> a = range(10)
>>> [x for x in a if x%2 == 0]
[0, 2, 4, 6, 8]
>>> [x*x for x in a if x%2 == 0]
[0, 4, 8, 36, 64]

We can even use multiple fors in single list comprehension.

>>> [(x, y) for x in range(5) for y in range(x) if (x+y)%2 == 0]
[(2, 0), (3, 1), (4, 0), (4, 2)]

Same as above, indented for clarity.

>>> [(x, y) 
...     for x in range(5) 
...     for y in range(x) 
...     if (x+y)%2 == 0]
...
[(2, 0), (3, 1), (4, 0), (4, 2)]

• Write a function mutate to compute all words generated by a single mutation on a given word. A mutation is defined as inserting a character, deleting a character, replacing a character, or swapping 2 consecutive characters in a string. For simplicity consider only letters from a to z.

  >>> words = mutate('hello')
  >>> 'helo' in words
  True
  >>> 'yello' in words
  True
  >>> 'helol' in words
  True
  

• Write a function nearly_equal to test whether two strings are nearly equal. Two strings a and b are nearly equal when a can be generated by a single mutation on b.

  >>> nearly_equal('python', 'perl')
  False
  >>> nearly_equal('python', 'jython')
  True
  >>> nearly_equal('man', 'woman')
  False
  

def exp(x, n):
    """Computes the result of x raised to the power of n."""
    if n == 0:
        return 1
    else:
        return x * exp(x, n-1)

Execution Pattern:

exp(2, 4)
+-- 2 * exp(2, 3)
|       +-- 2 * exp(2, 2)
|       |       +-- 2 * exp(2, 1)
|       |       |       +-- 2 * exp(2, 0)
|       |       |       |       +-- 1
|       |       |       +-- 2 * 1
|       |       |       +-- 2
|       |       +-- 2 * 2
|       |       +-- 4
|       +-- 2 * 4
|       +-- 8
+-- 2 * 8
+-- 16

Faster implementation of exponent function.

def fast_exp(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return fast_exp(x*x, n/2))
    else:
        return x * fast_exp(x, n-1)

Execution Pattern:

fast_exp(2, 10)
+-- fast_exp(4, 5) # 2 * 2
|   +-- 4 * fast_exp(4, 4)
|   |       +-- fast_exp(16, 2) # 4 * 4
|   |       |   +-- fast_exp(256, 1) # 16 * 16
|   |       |   |   +-- 256 * fast_exp(256, 0)
|   |       |   |             +-- 1
|   |       |   |   +-- 256 * 1
|   |       |   |   +-- 256
|   |       |   +-- 256
|   |       +-- 256
|   +-- 4 * 256
|   +-- 1024
+-- 1024
1024

The following function computes factorial of a number.

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

It looks quite similar to our exp function. Can you improve the execution time of this program by writing a fast_fact function? If not, explain why?

The sequence F(n) of Fibonacci numbers is defined by the recurrence relation:

F(n) = F(n-1) + F(n-2)
F(0) = 0 
F(1) = 1

And here is the Python version:

def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Execution Pattern:

                     fib(4)
             +---------+--------+
             |                  |
           fib(3)             fib(2)     
       +-----+-----+         +---+---+   
    fib(2)       fib(1)      |       |   
   +---+---+       |       fib(1)  fib(0)
   |       |       1         |       |
 fib(1)  fib(0)              1       1   
   |       |
   1       1

def count_change(amount, coins):
    """Counts the number ways in which amount can be made using the provided coins.

    Assumes that the coins are sorted in desceding order.
    """
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    elif not coins:
        return 0
    else:
        return count_change(amount-coins[0], coins) + \
            count_change(amount, coins[1:])

Lets try some examples.

>>> count_change(50, [50, 25, 10, 5])
11
>>> count_change(50, [50, 25, 10, 5, 1])
50
>>> count_change(100, [50, 25, 10, 5, 1])
292
>>> count_change(200, [50, 25, 10, 5, 1])
2435
>>> count_change(200, [50, 25, 10, 5, 2, 1])
58030

Consider the earlier fibonacci example.

def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Can we write a higher-order function to trace the execution of this function?

Here is the first attempt.

def trace(f):
    def g(x):
        print f.__name__, x
        value = f(x)
        print 'return', repr(value)
        return value
    return g

fib = trace(fib)
print fib(3)

Output:

fib 3
fib 2
fib 1
return 1
fib 0
return 1
return 2
fib 1
return 1
return 3
3

Lets try to pretty print the call log.

level = 0
def trace(f):
    def g(*args):
        global level
        indent = '|   ' * level + '|-- '

        argstr = ", ".join([repr(a) for a in args])
        print indent + f.__name__ + argstr

        level += 1
        value = f(*args)
        level -= 1

        print indent + ' return ' + repr(value)
        return value
    return g

Lets try our fib example.

fib = trace(fib)
print fib(4)

Output:

>>> print fib(4)
|-- fib(4)
|   |-- fib(3)
|   |   |-- fib(2)
|   |   |   |-- fib(1)
|   |   |   |   |-- return 1
|   |   |   |-- fib(0)
|   |   |   |   |-- return 1
|   |   |   |-- return 2
|   |   |-- fib(1)
|   |   |   |-- return 1
|   |   |-- return 3
|   |-- fib(2)
|   |   |-- fib(1)
|   |   |   |-- return 1
|   |   |-- fib(0)
|   |   |   |-- return 1
|   |   |-- return 2
|   |-- return 5
5

This can be very useful debugging tool.

@trace
def square(x):
    return x*x

@trace
def sum_of_squares(x, y):
    return square(x) + square(y)

print sum_of_square(3, 4)

Output:

|-- sum_of_squares(3, 4)
|   |-- square(3)
|   |   |-- return 9
|   |-- square(4)
|   |   |-- return 16
|   |-- return 25
25

• How can we get rid of the redundant computation in our fib function?
• How about caching the return values?

Doing this is very popular in functional programming world and it is called memoize.

def memoize(f):
    cache = {}
    def g(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return g

fib = trace(fib)
fib = memoize(fib)
print fib(4)

• Write a function profile, which takes a function as argument and returns a new function, which behaves exactly similar to the given function, except that it prints the time consumed in executing it.

  >>> fib = profile(fib)
  >>> fib(20)
  time taken: 0.1 sec
  10946
  

• Write a function vectorize which takes a function f and returns a new function, which takes a list as argument and calls f for every element and returns the result as a list.

  >>> def square(x): return x * x
  ...
  >>> f = vectorize(square)
  >>> f([1, 2, 3])
  [1, 4, 9]
  >>> g = vectorize(len)
  >>> g(["hello", "world"])
  [5, 5]
  

Iterators are special objects that can be iterated through.

>>> x = iter([1, 2, 3])
>>> x
<listiterator object at 0x1004ca850>
>>> x.next()
1
>>> x.next()
2
>>> x.next()
3
>>> x.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Iterators can be implemented as classes. Here is an iterator that works like xrange.

class yrange:
    def __init__(self, n):
        self.i = 0
        self.n = n

    def __iter__(self):
        return self

    def next(self):
        if self.i < self.n:
            i = self.i
            self.i += 1
            return i
        else:
            raise StopIteration()

Lets see it working:

>>> y = yrange(3)
>>> y.next()
0
>>> y.next()
1
>>> y.next()
2
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 14, in next
StopIteration

Many built-in functions accept iterators as arguments.

>>> list(yrange(3))
[0, 1, 2]

Generators simplifies creation of iterators.

def yrange(n):
    i = 0
    while i < n:
        yield i
        i += 1

Lets try it out.

>>> y = yrange(3)
>>> y.next()
0
>>> y.next()
1
>>> y.next()
2
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 14, in next
StopIteration

>>> list(yrange(3))
[0, 1, 2]

def integers():
    i = 1
    while True:
        yield i
        i = i + 1

def squares():
    for i in integers():
        yield i * i

def take(n, seq):
    """Returns first n values from the given sequence."""
    seq = iter(seq)
    result = []
    try:
        for i in range(n):
            result.append(seq.next())
    except StopIteration:
        pass
    return result

Lets try it.

>>> take(5, squares())
[1, 4, 9, 16, 25]

Generator expressions take generators to the next level.

See improved versions of squares and take functions using generator expressions.

def integers():
    i = 1
    while True:
        yield i
        i = i + 1

def squares():
    return (i*i for i in integers())

def take(n, seq):
    seq = iter(seq)
    return list(seq.next() for i in range(n))

See it in action.

>>> take(5, squares())
[1, 4, 9, 16, 25]