haskell - "applying a function for n times"可以使用 "exponentiating by squaring"完成吗？

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

我可以用 exponentiating by squaring方法在这里实现另一个 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'有时可能会有所改善。但是，其他时候它可能会浪费大量内存。