Sunday, January 4, 2009

W3R-3: Object-Oriented Reduce

We now have worked through deriving reduce in Python. In doing so, we have defined two closely related functions, fold1 and scan. Since they're so similar, it makes sense to briefly digress and consider bundling them together into a class. I won't make much use of the class in future installments of this series, but it is an interesting exercise to consider alternative definitions that might be a better fit to Python.

class Fold(object):

def __init__(self, function, init):
self.function = function
self.init = init

def __call__(self, acc, x):
return self.function(acc, x)

def scan(self, iterable):
function = self.function
acc = self.init
yield acc
for x in iterable:
acc = function(acc, x)
yield acc

def fold(self, iterable):
for x in self.scan(iterable): pass
return x
The Fold class is defined to take the function and initial value for the accumulator when the class is instantiated. This gives us some of the benefits we saw for the curried SML functions.

Putting the Fold class to use, we can define the sum and cumsum functions that we saw last time:
sum = Fold(operator.add, 0).fold
cumsum = Fold(operator.add, 0).scan
Perhaps more useful is to define something like<
add = Fold(operator.add, 0)
and then using add.scan and add.fold as needed.

Indeed, any function of two arguments could be given this treatment, so long as a sensible default (or identity) value can be given. Note that the min3 function from last time is not well suited to this sort of treatment, because it has no clear default value. However, the Fold class presents no additional difficulties over separate fold and scan functions.

1 As a reminder, fold is another name for reduce. We'll continue to reserve reduce as the name of the Python built-in function.

No comments: