Functional python

Sadly, I don't have an opportunity to write clojure at work, but I am able to write in python, so I've been tackling some common problems in python in a more functional style.  I've discovered that list comprehension, lambdas, map, and reduce are your friends.  Also, writing in a functional style often means writing less iterative code, and more recursive code.

So first things first, how can list comprehensions help?  Imagine if you a list of characters, and you want to combine all of them into a word.  Of course the pythonic way to do this would be:

example = [ 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
"".join(example)

This is of course perfectly valid.  A functional approach to this would be this:

reduce(lambda x,y: x + y, example)

In this case, the lambda is adding (concatenating) two strings together.  The reduce function takes the first two arguments, and then applies the result of that to the next argument.

Using the map() function is also handy, and can sometimes be easier to read then list comprehensions.  For example, the two below are equivalent:

[ x**2   for x in (1,2,3,4) ]

map(lambda x: x**2, (1,2,3,4))


However, what if you wanted to multiply some_collection[x] + another_collection[x]?  If you try to do this as a list comprehension, you won't get what you think:

[ x * y   for x in (1,2,3,4)  for y in (10,20,30,40)  ]  ## try it


Instead, you can use a map here:

map(lambda x,y: x*y, [1,2,3,4], [10,20,30,40])



While the examples above have been relatively trivial, here's a more complicated scenario.  Imagine that you are given an amount of change, and you are to calculate all the possible combinations of quarters, dimes, nickels and pennies you can get.  For example, if you are given 27 cents, you could have:

1 quarter, 2 pennies
2 dimes, 1 nickel, 2 pennies
1 dime, 2 nickels, 2 pennies
etc etc.


So how would you go about doing this?  When I first thought about this problem, I tackled it in the usual manner by trying to come up with an iterative imperative solution.  But I later decided (after the problem being fresh out of my mind) to come up with a recursive solution.  However, it's not only recursive, it's a mutual recursive problem.

So think about the problem like this.
1.  I have a total.  Given a number of quarters Q, I know the remainder of change (total - (25 * Q) )
2.  I have a remainder.  Given a number of dimes D, I know the remainder of change ( remainder - (10 * D))
3.  I have a remainder.  Given a number of nickels N, I know the remainder of change ( remainder - (5 * N))
4.  Any remainder left must be pennies

Do you see how all the problems are similar?  there are some gotchas however.  But below is the code representing my solution to this tricky problem.  I used a list here as return values so I could add lists together when one function call popped off the stack.




import pprint
def remainderNickels(total, nickels):
    if (nickels * 5) < total:
        newn = nickels + 1
        return remainderNickels(total, newn)
    else:
        return [ {'pennies' : total - (5 * (nickels - 1)), 'nickels' : nickels - 1 }]
   
def remainderDimes(total, dimes):
    remainder = total - (dimes*10)
    if (dimes * 10) < total:
        newd = dimes + 1
        if remainder >= 5:
            return remainderDimes(total, newd) + [ { 'remainder' : remainderNickels(remainder, 1), 'dimes' : dimes }]
        else:
            return [ {'pennies' : total - (10 * dimes), 'dimes' : dimes }]
    else:
        return [[]]

def remainderQuarters(total, quarters):
    remainder = total - (quarters*25)
    if (quarters * 25) < total:
        newq = quarters + 1
        if remainder >= 10:
            return remainderQuarters(total, newq) + [{ 'remainder' : remainderDimes(remainder, 1), 'quarters' : quarters} ]
        elif remainder >= 5:
            return remainderQuarters(total, newq) + [{ 'remainder' : remainderNickels(remainder, 1), 'quarters' : quarters} ]
        else:
            print "remainder = ", remainder
            return [ {'pennies' : remainder, 'quarters' : quarters }]
    else:
        return []
 
   
q = remainderQuarters(88, 1)
pp =pprint.PrettyPrinter()
pp.pprint(q)