如何多次组合两个函数？

Question

我需要写一段代码，这段代码能够接收一个数学函数和一个数字，然后输出一个重复组合的函数。

举个例子，如果 n=3，那么我希望得到 f(f(f(x))) 这样的结果。

但是当我运行我的代码时，出现了错误，我应该怎么修复它呢？

运行示例：

>>> repeated(lambda x:x*x, 2)(5)
624
>>> repeated(lambda x:x*x, 4)(3)
43046721

这是我的代码：

def repeated(f, n):
    g=f
    for i in range(n):
        g=lambda x: (g(g(x)))
    return (g)

Answer 1

我觉得这个问题挺有意思的，所以想了几天才来回答。我想出了几种通用的、符合Python风格的方法，可以让一个函数自己调用自己，正如问题中所描述的那样。最通用的解决方案就是 nest，它会返回一个生成器，这个生成器会依次返回函数在最初参数上的嵌套值。其他的解决方案都是基于这个方法的，不过装饰器也可以用上面提到的某种方法来实现。

#!/usr/bin/env python

"""
Attempt to create a callable that can compose itself using operators
Also attempt to create a function-composition decorator.

    f(x) composed once is f(x)
    f(x) composed twice is f(f(x))
    f(x) composed thrice is f(f(f(x)))

This only makes sense at all if the function takes at least one argument:

    f() * 2 -> f(?)

But regardless of its arity, a function can only return exactly one value (even if that value is iterable). So I don't think it makes sense for the function to have >1 arity, either. I could unpack the result:

    f(x, y) * 2 -> f(*f(x, y))

But that introduces ambiguity -- not every iterable value should be unpacked. Must I inspect the function to tell its arity and decide whether or not to unpack on the fly? Too much work!

So for now, I just ignore cases other than 1-arity.
"""
def nest(func, arg):
    """Generator that calls a function on the results of the previous call.
    The initial call just returns the original argument."""
    while True:
        yield arg
        arg = func(arg)

def compose(n):
    """Return a decorator that composes the given function on itself n times."""
    if n < 1: raise ValueError
    def decorator(func):
        def nested(arg):
            gen = nest(func, arg)
            for i in range(n):
                next(gen)
            return next(gen)
        return nested
    return decorator

class composable(object):
    """A callable that can be added and multiplied."""
    def __init__(self, func):
        self.func = func
    def __add__(self, func2):
        """self(func2(x))"""
        def added(a):
            return self(func2(a))
        return composable(added)
    def __mul__(self, n):
        """self * 3 => self(self(self(a)))"""
        def nested(a):
            gen = nest(self, a)
            for i in range(n):
                next(gen)
            return next(gen)
        return composable(nested)
    def __call__(self, *args, **kwargs):
        return self.func(*args, **kwargs)

@compose(2)
def sq(x):
    return x*x

@compose(4)
def qu(x):
    return x*x

@composable
def add1(x):
    return x + 1

compset = composable(set)

assert (compset + str.split)('abc def') == set(['abc', 'def']), (compset + str.split)('abc def')
assert add1(1) == 2, add1(1)
assert (add1 + (lambda x: x * x))(4) == 17, (add1 + (lambda x: x * x))(4)
assert (add1 * 3)(5) == 8, (add1 * 3)(5)

assert 625 == sq(5), sq(5)
assert 43046721 == qu(3), qu(3)

Answer 2

根据你任务的具体情况（比如编程课），你可能会对这个简单的解决方案感兴趣：

def repeated(f,  n):
  if n < 1:
    raise ValueError()
  elif n == 1:
    return f
  else:
    return lambda x: repeated(f, n-1)(f(x))

这是一个简单的递归解决方案，它更直接地符合要求。如果你已经了解了一些高级函数，比如 reduce，我建议你可以参考Martijn Pieters的解决方案。不过，这个方法也是有效的：

>>> repeated(lambda x:x*x, 2)(5)
625
>>> repeated(lambda x:x*x, 4)(3)
43046721

Answer 3

返回一个新的函数，这个函数只有在被调用的时候才会重复执行：

def repeated(f, n):
    def repeat(arg):
        return reduce(lambda r, g: g(r), [f] * n, arg)
    return repeat

reduce() 方法利用函数列表 f 中的函数引用，来创建合适数量的嵌套调用，开始时用 arg 作为第一个参数。

示例：

>>> def repeated(f, n):
...     def repeat(arg):
...         return reduce(lambda r, g: g(r), [f] * n, arg)
...     return repeat
... 
>>> repeated(lambda x:x*x, 2)(5)
625
>>> repeated(lambda x:x*x, 4)(3)
43046721

一个不使用 reduce() 的版本可以是：

def repeated(f, n):
    def repeat(arg):
        res = arg
        for _ in range(n):
            res = f(res)
        return res
    return repeat