5

I was working on project euler problem 14 and as a first attempt I whipped up this brute-force solution:

def collatz(n, memo={1: [1]}):
    if n not in memo:
        memo[n] = [n] + collatz(3 * n + 1 if n % 2 else n // 2)
    return memo[n]

def p014():
    return max(xrange(1, 10**6), key=lambda n: len(collatz(n)))

My question is about that lambda, I'm usually reluctant to use them but I don't know any elegant way to avoid it in this case. Is there something in functools or other to chain two callables, or any other neat alternative I'm missing?

wim
  • 338,267
  • 99
  • 616
  • 750
  • Just so it's said, you can define a regular function :) – Lev Levitsky Nov 04 '12 at 14:19
  • Of course, I'm aware of that. I was looking more for a function composition trick. In mathematical terms, I would write it like `key=len \cdot collatz` (sorry don't know any markup for a center dot) – wim Nov 04 '12 at 14:21
  • 5
    this is the perfect case for an anonymous function. Just use it – JBernardo Nov 04 '12 at 14:25
  • Why are you creating a dictionary containing the entire chains? Aren't you just interested in the chain lengths? – arshajii Nov 04 '12 at 14:25
  • 1
    @JBernardo No, it's a perfect case for a higher-order function/combinator. –  Nov 04 '12 at 14:26
  • Writing a function composition function would be pretty simple, something like `def composite(func1, func2): return lambda n: func1(func2(n))` should work, assuming `func2` takes one argument of course. I'd agree with @JBernardo though, there's nothing wrong with the anonymous function here – Strigoides Nov 04 '12 at 14:26
  • @delnan I meant the "when you need two callables" case. – JBernardo Nov 04 '12 at 14:27
  • 1
    @Strigoides Using a lambda to avoid using a lambda? I'm not sure the OP will buy that :) – Lev Levitsky Nov 04 '12 at 14:34
  • 2
    [`compose = lambda *funcs: lambda x: reduce(lambda y, f: f(y), reversed(funcs), x)`](http://ideone.com/plzPHa) (`compose()` is not recommended to use whatever implementation (the code becomes less readable)) – jfs Nov 04 '12 at 14:50
  • @J.F.Sebastian That's a matter of personal taste. Many functional programmers find point-free style to be much more readable. – Marcin Nov 04 '12 at 14:52
  • @A.R.S. good point. with your suggestion, i was able to get great performance boost by memoising the length rather than the sequence, and then using the simple `max(xrange(1, 10**6), key=collatz_length)`. I am still interested in the answers to the function composition issue, though. – wim Nov 04 '12 at 15:07
  • @Marcin: language dictates preferable style. Python is not Factor, J or Haskell. It is not just a matter of personal taste if you expect others to read your code. – jfs Nov 04 '12 at 17:43
  • 2
    @J.F.Sebastian Language may, to an extent, dictate style, but there's nothing inherent in a python pointfree programme that renders it less readable than e.g. in Haskell. Yes, the python programmers who will find that convenient are a subset of all python programmers, but that is also true of completely idiomatic code. – Marcin Nov 04 '12 at 18:16

2 Answers2

6

It would be lovely if there were a compose function -- perhaps in functools. There is not, nor do I expect there will be, alas. In the words of Raymond Hettinger,

It has been previously discussed and rejected in other forums. One of the issues is that the usual mathematical order is unintuitive and not self-documenting -- i.e. is compose(f,g) the same as f(g(x)) or g(f(x))? Also, it is already dirt simple to create your own compose function or to do the composition directly: h = lambda x: f(g(x)).

Here are two simple implementations of compose as a callable class that you may find useful though:

# Scott Daniels, http://code.activestate.com/recipes/52902-function-composition/
# Lightly edited for style.
class Compose(object):
    '''Compose functions. compose(f,g,x...)(y...) = f(g(y...),x...))'''
    def __init__(self, f, g, *args, **kwargs):
        self.f = f
        self.g = g
        self.pending = args[:]
        self.kwargs = kwargs.copy()

    def __call__(self, *args, **kwargs):
        return self.f(self.g(*args, **kwargs), *self.pending, **self.kwargs)


class Starcompose:
    '''Compose functions. Starcompose(f,g,x...)(y...) = f(*g(y...),x...))'''
    TupleType = type(())

    def __init__(self, f, g, *args, **kwargs):
        self.f = f
        self.g = g
        self.pending = args[:]
        self.kwargs = kwargs.copy()

    def __call__(self, *args, **kwargs):
        mid = self.g(*args, **kwargs)
        if isinstance(mid, self.TupleType):
            return self.f(*(mid + self.pending), **self.kwargs)
        return self.f(mid, *self.pending, **self.kwargs)

Also, see the functional package, which inspired this very simple compose_many function of mine a while ago:

def compose(f1, f2):
    def composition(*args, **kwargs):
        return f1(f2(*args, **kwargs))
    return composition

def compose_many(*funcs):
    return reduce(compose, funcs)
Community
  • 1
  • 1
senderle
  • 145,869
  • 36
  • 209
  • 233
  • Note that http://pypi.python.org/pypi/functional/0.7.0 contains a compose function. – Marcin Nov 04 '12 at 14:50
  • @Marcin, thank you! I knew about that and was looking for that but it wasn't popping up in my google searches. I thought perhaps its author had removed it. – senderle Nov 04 '12 at 14:52
  • The oakwinter.com domain has expired, so the only documentation is now in the code. Not sure what's up with the author, Collin Winter. – Marcin Nov 04 '12 at 14:53
  • great answer with lots of food for thought. – wim Nov 04 '12 at 14:58
2

It might be more pythonic to write this as a generator:

def p014():
    length, n = max(
        (len(collatz(n)), n)
        for n in xrange(1, 10**6)
    )
    return n
Eric
  • 95,302
  • 53
  • 242
  • 374