haskell - 如何加快(或内存)一系列相互递归的功能

我有一个程序，它产生一系列函数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然后向上工作)？

最佳答案

您可能会发现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有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应该可以加快速度。

关于haskell - 如何加快(或内存)一系列相互递归的功能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10135287/