重复函数应用

Question

I'm having trouble with a question which follows: Write a recursive function repeatedlyApply that takes as arguments a function f of one argument and a positive integer n. The result of repeatedlyApply is a function of one argument that applies f to that argument n times.

So, for example, we would have

repeatedlyApply(lambda x: x+1,10)(100) ==> 110

You may assume that the following function has been defined. You don't have to use it, but it can contribute to a pretty solution.

def compose(f,g):
    return lambda x: f(g(x))

So far i've written this

def compose(f,g):
    return lambda x: f(g(x))

def recApply(f,n):
    for i in range(n):
        return recApply(compose(f,f), n-1)
    return f

I'm going wrong somewhere because using the above example recApply(lambda x: x+1,10)(100) i get 1124.

Help much appreciated

- Benji

---

你最终添加了 1024 而不是 10。想一想为什么会得到 2 的幂次方。 - sverre

Answer 1

正确答案是:

def recApply(func, n):
    if n > 1:
        rec_func = recApply(func, n - 1)
        return lambda x: func(rec_func(x))
    return func

输出结果如下：

>>>> print recApply(lambda x: x+1,10)(100)
110

- berni

Answer 2

我有一个基于lambda的解决方案：

>>> f = lambda x: x + 10
>>> iterate = lambda f, n, x : reduce(lambda x, y: f(x), range(n), x)
>>> iterate(f, 10, 3)
103
>>> iterate(f, 4, 4)
44
>>> f10 = lambda x: iterate(f, 10, x)
>>> f10(5)
105

- Emmanuel

Answer 3

你的函数还需要一些改进：

• 你在for循环中使用了return，这会导致你立即返回而不是运行整个循环。
• 你在for循环中使用了递归调用，这样做会进行过多的迭代。请选择其中一个。
• 当你将函数组合叠加在一起时要小心，你正在进行幂次组合而不是线性组合。

你能告诉我们你想做什么吗？

编辑：由于其他人都发布了答案：

recApply = lambda f, n: lambda x: x if n == 0 else recApply(f, n-1)(f(x))

- sverre

---

代码似乎应该是：recApply = lambda f, n: lambda x: x if n == 0 else recApply(f, n-1)(f(x))，否则返回值永远不会改变。 - xiao 啸

Answer 4

我猜这是某种练习。你可以用几种方法来完成它，这里有一个简短的：

>>> repeatedlyApply = lambda f, n: reduce(lambda f1, f2: compose(f1, f2), [f]*n)
>>> repeatedlyApply(lambda x: x+1,10)(100)
110

- shygon