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番目を呼び出したときに、すでに計算されている場合fは（n-1）番目を再計算しないことを意味することを素朴に望んでいました（関数である場合とそうでない場合のように）。プログラム全体を分解せずにこれをメモする方法はありますか（たとえば、関連するすべての引数を評価してから上向きに作業するなど）？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))

これがプログラム全体をバラバラにするものと見なされないことを願っています。

あなたのコメントへの返信：

これは私が思いつくことができる最高です。テストされていませんが、正しい方向に機能しているはずです。

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を評価してから、上向きに作業する）？

これは「プログラム全体をリッピングする」という意味かもしれませんが、これが（ATMをテストできないと思いますが）fooX共有できるソリューションです。

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 に答える