Python Functional Programming

Lecture 1
Lecture 2

# Do you remember this code from previous lecture (lecture 2)
def make_adder(n=1):
    return lambda x: x + n

one_adder = make_adder() # actually creates: one_adder = lambda x: x + 1
one_adder(1)

"""
1. List/Dict comprehension

"""

# [{do job using 'for' variable} {'for' cycle} {filter predicate (optional)}]

# for lists
i_all = [i for i in range(0, 10)]
i_all_even = [i for i in range(0, 10) if i % 2 == 0]

# for dict
x_squared_dict = {item: item * item for item in range(0, 4)}

"""
2. Map (aka transform) function

map: this function takes a unary function and some list/iterable
of values and produces a list/iterable of mapped/transformed values based on
substituting each value with the result of calling the parameter function
on that value.

map({function}, {iterable+}) returns transformed sequence
"""

map(lambda x : x**2, range(1, 5))
map(lambda x,y: x*y, range(1, 5), range(1, 5))

"""
3. Filter (aka accumulate)

filter: this function takes a predicate (a unary function returning a bool)
and some list/iterable of values and produces a list/iterable with only
those values for which the predicate returns True.

filter({predicate function}, {iterable})
"""

# filter({predicate for even}, [i for i in range(2,50)])

def is_even(x):
    return x % 2 == 0

# Remember how function is passed
filter(is_even, [i for i in range(2,50)])

# Using lambda. Do not forget () around!
filter((lambda x: x % 2 == 0), [i for i in range(2,50)])

"""
4. Reduce

reduce: this function is different than the previous two: it
takes a binary function and some list/iterable of values and typically produces
a single value: it reduces or accumulates its arguments into a single value.

By default, the first item in the sequence initialized the starting value.
"""

# function with two parameters is a binary function
reduce((lambda x, y: x * y), range(1, 5))
# (((1 * 2) * 3) * 4)

# Here is the 'for' loop version
L = range(1, 5)
result = L[0]
for x in L[1:]:
    result = result * x
    print result

reduce(lambda x,y : x - y, [1, 2, 3])
# ((1 - 2) - 3)

# NOTE: Technically, this is called LEFT reduction/accumulation because the operators are
# applied left to right.

def max(x, y):
    return x if x > y else y

# Then, calling

reduce(max, [4, 2, -3, 8, 6])

# is equivalent to max(max(max(max(4,2),-3),8),6) which evaluates (left to right)
# as follows, to compute the maximum of the entire list of values.
#
# max(max(max(max(4,2),-3),8),6) -> max(max(max(4,-3),8),6) ->
# max(max(4,8),6) -> max(8,6) -> 8

# Here is a concrete example of a function style of programming, using map,
# filter, and reduce.

# This expression computes the length of the longest line in
# a file.
reduce(max, map(lambda l: len(l.strip()), open('recursion.txt')))

# To return the longest line, not the length of the longest line, we could alter
# the computation slightly, as follows.
reduce(lambda x,y: x if len(x) >= len(y) else y,
       map(lambda l: l.strip(), open('recursion.txt')))

# Collect all files that contains a word
filter(lambda x: 'Problems:' in x,                      # **fixed**
       map(lambda l: l.strip(), open('recursion.txt'))) # **fixed**

# REMEMBER: Your functions should be as general as possible!

def search_in(file_name):
    return filter(lambda x: 'Problems:' in x ,
              map(lambda l: l.strip(), open(file_name)))

# not so bad - you can pass any file
search_for_prblems = search_in('recursion.txt')
search_for_prblems

# even better search for a different text
def search_in(file_name, text):
    return filter(lambda x: text in x ,
              map(lambda l: l.strip(), open(file_name)))

search_for = search_in('recursion.txt', 'Define')
search_for

# Could we divide file from text?

# In fist phase we set file_name in second text => closures baby!

# Returns a function(closure with file_name fixed) with one parameter
def search_in(file_name):
    return lambda text: filter(lambda x: text in x ,
                           map(lambda l: l.strip(), open(file_name)))

search_for = search_in('recursion.txt')
search_for('Define')

# Tip: Think of map as equivalent to one 'for' cycle

# I. Let's write 'combine_all' from previous lecture homework in Lisp way

# 1. map(map({func(x, y)}, ylist), xlist)

# 2. map(map((lambda x,y: [x, y]), ylist), xlist)

# 3. Use closure to pre-set x:
#    map((lambda x: map((lambda y: [x, y])), ylist)), xlist)

# 4. Check up to now
def combine_all(xlist, ylist):
    return map((lambda x:
            map((lambda y: [x, y]), ylist)),
           xlist)

combine_all(['a', 'b'], [1, 2])
# return two lists: [[['a', 1], ['a', 2]], [['b', 1], ['b', 2]]]

# 5. flatten one level -> [[1, 2], [3, 4]] to become [1, 2, 3, 4]
import operator
def combine_all(xlist, ylist):
    return reduce(operator.add, (map((lambda x:
                                  map((lambda y: [x, y]), ylist)),
                                 xlist)))

# II. Let's write 'combine_all' from previous lecture homework in Python way

# list comprehension could be multi-level
def combine_all(xlist, ylist):
    return [[x, y] for x in xlist for y in ylist]

# Tip: Always use list comprehension when want to return list

'''
1. Kinds of iteration:
- for, while (iterators, generators)
- map (high order functions)
- recursion - we strive to be tail recursion(later in this lecture)
'''

'''
2. What is recursion?

Recursion is a programming technique in which a call to a function results in
another call to that same function. Recursion means "defining something in terms of itself".

It is not only for functions - also for structures e.g. lists:

list = element | list
'''

# How can we present a list? list = element + rest of list
lst = [1, 2, 3]
lst2 = [lst[0]] + lst[1:]

# TIP: Remember that lst[0] returns element not list so we have to convert it to list!

# Do you remember that?
a = 'abc'
a[0]

# How about strings? It is a bit easy:
s = 'abc'
s2 = s[0] + s[1:]

'''
3. Lists and recursion

If you have list(string is also a list) data structure you can use recursion.
'''

# Here is how we structure recursive function:

# Phase One - stop condition
def reverse(s):
    if s == '':
        return ''
    else:
        # Recur to solve a smaller problem
        # Use the solution of the smaller problem to solve the original problem
        pass

# Phase Two - use rest of the list s[1:]
def reverse(s):
    if s == '':
        return ''
    else:
        # Use the solution of reverse(s[1:]) to solve the original problem
        pass

def reverse(s):
    if s == '':
        return ''
    else:
        return reverse(s[1:]) + s[0]

# Pythonic way using if

def reverse(s):
    return '' if s == '' else reverse(s[1:]) + s[0]

# Example
reverse('abcd')

'''
2. What is tail recursion and why it is better?

'''

# Which one is better - iteration or recursion?

def recsum(x):
    if x == 1:
        return x
    else:
        return x + recsum(x - 1)

# Evaluation description
#
# recsum(5)
# 5 + recsum(4)
# 5 + (4 + recsum(3))
# 5 + (4 + (3 + recsum(2)))
# 5 + (4 + (3 + (2 + recsum(1))))
# 5 + (4 + (3 + (2 + 1)))
# 15

# Not tail recursive either
def bad_factorial(n):
    if n == 0:
        return 1
    return n * bad_factorial(n - 1)


# Python limits the number of times any recursive function can call itself.

# Convert recursion to tail recursion introducing accumulator (aka pumping)

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

# TCO (Tail Call Optimization) is the process by which a smart compiler can make a call to
# a function take no additional stack space.

# REMEMBER: Python do not do tail-call optimization!
# Read why: http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html