如何加速(或记忆)一系列相互递归的函数

Question

我有一个程序,它产生一系列功能f,g如下所示:

step (f,g) = (newF f g, newG f g)

newF f g x = r (f x) (g x)
newG f g x = s (f x) (g x)

foo = iterate step (f0,g0)

其中R和S是一些无趣的功能f x和g x.我天真地希望,有foo是一个列表将意味着当我打电话的第n个f它不会重新计算(N-1)个f,如果它已经计算出它(如将如果发生f和g没有功能).有没有办法记住这一点而不会将整个程序拆开(例如评估f0和g0所有相关论点,然后向上工作)？

Answer 1

您可能会发现Data.MemoCombinators很有用（在 data-memocombinators 包中）。

您没有说明您的参数类型f和g采用的参数类型 - 如果它们都采用整数值，那么您将像这样使用它：

import qualified Data.MemoCombinators as Memo

foo = iterate step (Memo.integral f0, Memo.integral g0)

如果需要，您也可以记住每个步骤的输出

step (f,g) = (Memo.integral (newF f g), Memo.integral (newG f g))

我希望您不会认为这会破坏整个程序。

回复您的评论：

这是我能想到的最好的办法。它未经测试，但应该按照正确的方式工作。

我担心在Double和 之间进行转换Rational是不必要的低效——如果有一个我们可以使用的Bits实例的话。因此，这最终可能对您没有任何实际用途。DoubleMemo.bits

import Control.Arrow ((&&&))
import Data.Ratio (numerator, denominator, (%))

memoV :: Memo.Memo a -> Memo.Memo (V a)
memoV m f = \(V x y z) -> table x y z
  where g x y z = f (V x y z)
        table = Memo.memo3 m m m g

memoRealFrac :: RealFrac a => Memo.Memo a
memoRealFrac f = Memo.wrap (fromRational . uncurry (%))
                           ((numerator &&& denominator) . toRational)
                           Memo.integral

一种不同的方法。

你有

step :: (V Double -> V Double, V Double -> V Double)
     -> (V Double -> V Double, V Double -> V Double)

你把它改成怎么样

step :: (V Double -> (V Double, V Double))
     -> (V Double -> (V Double, V Double))
step h x = (r fx gx, s fx gx)
  where (fx, gx) = h x

还有改变

foo = (fst . bar, snd . bar)
  where bar = iterate step (f0 &&& g0)

希望共享fx和gx应该会带来一点加速。