Cómo acelerar (o memoize) una serie de funciones mutuamente recursivas

Question

Tengo un programa que produce una serie de funciones f y g que se parece a lo siguiente:

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) 

Donde r y s son algunos sin interés funciones de f x y g x. Ingenuamente esperaba que tener foo ser una lista significaría que cuando llamo al n'th f no volverá a calcular el (n-1) th f si ya lo ha calculado (como hubiera sucedido si f y g no fueran funciones). ¿Hay alguna manera de memorizar esto sin romper todo el programa (por ejemplo, evaluando f0 y g0 en todos los argumentos relevantes y luego trabajando hacia arriba)?

Answer 1

Puede encontrar Data.MemoCombinators útil (en el paquete data-memocombinators).

Usted no dice qué tipos argumento de su toma y fg --- si ambos toma valores enteros, entonces sería utilizar de esta manera:

import qualified Data.MemoCombinators as Memo 

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

Si es necesario, se podría memoise la salida de cada paso también

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

Espero que no vea esto como una ruptura de todo el programa.

---

En respuesta a su comentario:

Esto es lo mejor que puedo llegar a. No se ha probado, pero debería funcionar en la línea correcta.

Me preocupa que la conversión entre DoubleRational y es innecesariamente ineficaz --- si había una instancia Bits para Double podríamos utilizar Memo.bits lugar. Por lo tanto, esto podría no ser útil para ti en última instancia.

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 

---

Un enfoque diferente.

Tienes

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

¿Qué cambia eso a

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 

y también cambiar

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

Esperemos que la compartían fx y gx debería resultar en un poco de velocidad -arriba.

Answer 2

¿Hay alguna manera de memorizar esto sin separar todo el programa (por ejemplo, evaluando f0 y g0 en todos los argumentos relevantes y luego trabajando hacia arriba)?

Esto puede ser lo que quiere decir con "rasga todo el programa aparte", pero aquí es una solución en la que (creo, pero no puedo probar ATM) fooX puede ser compartido.

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) 

No sé si eso conserva el espíritu de su implementación original.