PyCon India 2011
September 16, 2011
With lot of interesting examples!
>>> 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 for
s 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
Defining solution of a problem in terms of the same problem, typically of smaller size, is called recursion.
Recursion makes it possible to express solution of a problem very concisely and elegantly.
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)
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)
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)
fib(4)
+---------+--------+
| |
fib(3) fib(2)
+-----+-----+ +---+---+
fib(2) fib(1) | |
+---+---+ | fib(1) fib(0)
| | 1 | |
fib(1) fib(0) 1 1
| |
1 1
How many different ways can we make change of 50 using coins of denomination 50, 25, 10 and 5?
50
25 + 25
25 + 10 + 10 + 5
25 + 10 + 5 + 5 + 5
25 + 5 * 5
5 * 10
4 * 10 + 2 * 5
3 * 10 + 4 * 5
2 * 10 + 6 * 5
1 * 10 + 8 * 5
10 * 5
11 ways.
What will be the number if we also have coin of denomination 1? Can we write a program to compute that?
The number of ways to change amount A
is equal to:
A
using all but the largest coin, plusA - D
using all kinds of coins, where D
is the denomination of the largest kind of coin.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
Functions that take functions as arguments or return other functions.
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
fib
function? 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)
Output:
|-- fib(4)
| |-- fib(3)
| | |-- fib(2)
| | | |-- fib(1)
| | | | |-- return 1
| | | |-- fib(0)
| | | | |-- return 1
| | | |-- return 2
| | |-- return 3
| |-- return 5
5
Notice that the redundant computation is gone now.
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]
Table of Contents | t |
---|---|
ExposÃ© | ESC |
Full screen slides | e |
Presenter View | p |
Source Files | s |
Slide Numbers | n |
Toggle screen blanking | b |
Show/hide slide context | c |
Notes | 2 |
Help | h |