使用"通过平方取幂"可以"应用n次函数"吗？

Question

给定类型的函数f :: a -> a,我们可以生成一个适用f于n时间的函数:

nTimes :: Int -> (a -> a) -> (a -> a)
nTimes 0 _ = id
nTimes 1 f = f
nTimes n f = f . nTimes (n-1) f

我可以通过平方法在这里使用取幂来实现另一个nTimes函数:

nTimes' :: Int -> (a -> a) -> (a -> a)
nTimes' = nTimes'' id
    where
        nTimes'' acc n f
            | n == 0    = acc
            | even n    = nTimes'' acc (n `div` 2) (f . f)
            | otherwise = nTimes'' (acc . f) (n-1) f

我的问题是:

• 不要nTimes和nTimes'总是产生相同的结果？
• 会nTimes'更快吗？

Answer 1

虽然它们是等价的,但如果ntimes'在任何实际情况下实际上更快或节省内存,我会感到非常惊讶.问题是,与x * x通过平方的普通取幂加倍不同,f . f实际上并不共享任何在应用时所做的实际工作f.它仍然要打开在末端插入施加最外层单f由所有其余构造参数以某种方式.而ntimes (n-1) f x将是有关的最紧凑表示你可以有剩余的,直到它自身实际需要进行评估,这将需要应用的最左边f到的表示ntimes (n-2) f x,等等.

编辑:我要补充的是,如果你是这样做可能会显著改变记忆化,即替换f . f的memo (f . f)一些备忘录,组合子,用于修改功能记住它的结果.在这种情况下,可以共享实际工作,这个版本有时ntimes' 可能会有所改进.但有时候它可能会浪费大量的内存.

Answer 2

这将产生在两种情况下相同的结果,因为这两个*和.是相关联的运营商.

然而,"加速"并不是你想到的加速.平方的指数是好的,因为它减少了*操作符的应用次数,从线性到对数次数.在这种情况下,您将减少.应用运算符的次数,从线性到对数次数.

然而,就像ØrjanJohansen所说的那样*,.运算符并没有真正做太多 - 它只需要两个函数值,并输出一个新的函数值,它实际上包含了给定的两个函数和一些代码.

nTimes'当应用于值时,您获得的结果函数必须仍然运行fn次.因此,实际运行所得函数没有改进,只是改进了构造所得函数的过程..