Thursday, June 25, 2015

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

No comments:

algorithms (1) cpp (3) cv (1) daily (4) emacs (2) freebsd (4) java (3) javascript (1) JSON (1) linux (2) Lisp (7) misc (8) programming (16) Python (4) SICP (1) source control (4) sql (1) думи (8)