6

我有一个程序，它产生一系列函数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)

f x其中 r 和 s 是和的一些无趣的函数g x。我天真地希望拥有foo一个列表意味着当我调用第 n个时，如果它已经计算过它，它将不会重新计算第 (n-1) 个（如果不是函数就会发生这种情况f）。有没有办法在不将整个程序分开的情况下记住这一点（例如，评估所有相关参数，然后向上工作）？ffgf0g0

4

2 回答 2

0

您可能会发现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))

我希望你不要把这看作是把整个程序撕成碎片。

回复您的评论：

这是我能想到的最好的。它未经测试，但应该沿着正确的路线工作。

我担心在 and 之间进行转换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应该会导致一些加速。

于 2012-04-13T06:20:50.223 回答
0

有没有办法在不将整个程序分开的情况下记住这一点（例如，在所有相关参数上评估 f0 和 g0 然后向上工作）？

fooX这可能是您所说的“将整个程序分开”的意思，但这是一个可以共享的解决方案（我相信但无法测试 ATM） 。

nthFooOnX :: Integer -> Int -> (Integer, Integer)
nthFooOnX x = 
    let fooX = iterate step' (f0 x, g0 x)
     in \n-> fooX !! n

step' (fx,gx) = (r fx gx, s fx gx)

-- testing definitions:
r = (+)
s = (*)
f0 = (+1)
g0 = (+1)

我不知道这是否保留了您最初实施的精神。

于 2012-04-13T20:03:10.493 回答