folding with python

Solving this problem the functional way =>

Find if a sorted list of positive numbers has duplicates.

>>> def has_dups(nums):

...     return reduce (lambda x,y: ( x[0] or (y == x[1]), y), nums, (False,0))[0]

... 

>>> has_dups([1])

False

>>> has_dups([1,1])

True

>>> has_dups([1,1,1])

True

>>> has_dups([1,2,4])

False

>>> has_dups([1,2,2])

True

>>> has_dups([1,2,2,3,4])

True

>>> 

From the definition of reduce:

reduce(function, iterable[, initializer])

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the iterable. If the optional initializer is present, it is placed before the items of the iterable in the calculation, and serves as a default when the iterable is empty. If initializer is not given and iterable contains only one item, the first item is returned. Roughly equivalent to:

To solve the problem, we need to check if two adjacent items have the same value. To do this the functional way, we walk through the list using the reduce operator. At each point in the list, the reduce operator applies the user supplied function to the previous output(x) and the current item(y) of the list.

We need to remember if we see two adjacent items, and pass it as the output. But we also have to pass the current value so that at the next step, reduce can evaluate the given function. So we have a tuple as output from the function :

(truth value whether we have seen two adjacent items, current item)

We need to pass an initial value for the tuple (initializer). The truth value would be False initially, and we pass a zero as all elements of the list are positive. (False, 0)

So within the lambda, we need to check if the current item is the same as the previous item (y == x[1]) but if we had already met this condition (x[0]), we need to pass this along.

One of the drawbacks of the fold is that there is no quick break from traversing the list once we find a duplicate. It is possible to raise an exception in lambda and force a termination that way, but I don't know of a clean way to terminate the walk of the complete list.