haskell - 如何加速(或内存)一系列相互递归的函数

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 take --- 如果它们都取整数值，那么你会像这样使用它:

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 Double 的实例我们可以使用 Memo.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应该会导致一点加速。