Saturday, May 19, 2012

Simplifying nested loops

I've recently been working my way through two Udacity courses, CS212, Design of Computer Programs, taught by Peter Norvig, and CS262, Programming Languages, taught by Westley Weimar and have become in interested in Functional Programming. So far, haven't found much reference material on the approach but I did come across some Charming Python articles that are very useful.

This is a re-work of one example from the first article, found under Eliminating Side-effects
# Examples of using functional programming in place of loops/control statements
# Reference: http://gnosis.cx/publish/programming/charming_python_13.html

# A larger example of converting IMPERATIVE program to FP
# Goal:
#   list pairs of numbers whose products are > 25
#
# Standard imperative approach, the 'more stuff' lines
# represent spots where other processing might occur in
# a full program and represent spots where the key variables
# may take on different values; as well, when this section
# of code is complete, all the variables may have values
# that may or not be expected, or wanted, in the remaining code

xs = (1,2,3,4)          # list of numbers
ys = (10, 15, 3, 22)    # second list of numbers
bigmuls = []            # list to hold results
# ... more stuff ....
for x in xs:
    for y in ys:
        # ... more stuff ....
        if x * y > 25:
            bigmuls.append( (x,y) )

print('Imperative Programming result:', bigmuls)            
            
# the same using an FP approach
#    bigmuls = lambda xs,ys: filter(lambda (x,y):x*y > 25, combine(xs,ys))
#    combine = lambda xs,ys: map(None, xs*len(ys), dupelms(ys,len(xs)))
#    dupelms = lambda lst,n: reduce(lambda s,t:s+t, map(lambda l,n=n: [l]*n, lst))
#
# Note:
#    the methods given in the article can be reduced to one line
#    by using itertools.product() which produces 'all pairs' from two given lists
#    essentially, this was the purpose of the 'dupelms() and 'combine()' functions
#    in the original article. 
#    A key advantage of this approach:
#        the original variable value NEVER change, so no possible side-effects


from itertools import product

bigmuls = lambda xs,ys: filter(lambda pair: pair[0]*pair[1] > 25, product(xs,ys) )

print('Functional Programming result:', list(bigmuls(xs,ys)))

# Or an even better example, just use a 'list comprehension' as a one-off need

res = [a for a in product(xs,ys) if a[0]*a[1] > 25]
print('List Comprehension result    :', res)

Wednesday, May 9, 2012

Convert list of lists to single list

This example is based on a Udacity CS262 discussion forum post.

  messedUp = [['one'], ['two'],['three'], ['four']]
  return [item for inner in messedUp for item in inner]
  
  Result:   ['one', 'two', 'three', 'four']