How to speed up (or remember) a number of mutually recursive functions

Question

I have a program that creates a series of f and g functions that look like this:

 step (f,g) = (newF fg, newG fg) newF fgx = r (fx) (gx) newG fgx = s (fx) (gx) foo = iterate step (f0,g0) 

Where r and s are some uninteresting functions from fx and gx . I naively hoped that having foo list would mean that when I call n'th f , he would not compromise (n-1) th f if he already calculated it (as it would be if f and g were not functions). Is there a way to remember this without breaking the entire program (for example, evaluating f0 and g0 with all the relevant arguments and then working up)?

Answer 1

You may find Data.MemoCombinators useful (in the data-memocombators package).

You do not say which argument your f and g , if they both take integer values, then you will use it as follows:

 import qualified Data.MemoCombinators as Memo foo = iterate step (Memo.integral f0, Memo.integral g0) 

If necessary, you can also save the output of each step.

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

Hopefully you won't see this breaking the whole program.

---

In response to your comment:

This is the best I can think of. It has not been tested, but should work on the correct lines.

I'm worried that converting between Double and Rational uselessly inefficient --- if there was a Bits instance for Double , we could use Memo.bits . Therefore, it may not ultimately be useful to you.

 import Control.Arrow ((&&&)) import Data.Ratio (numerator, denominator, (%)) memoV :: Memo.Memo a -> Memo.Memo (V a) memoV mf = \(V xyz) -> table xyz where gxyz = f (V xyz) table = Memo.memo3 mmmg memoRealFrac :: RealFrac a => Memo.Memo a memoRealFrac f = Memo.wrap (fromRational . uncurry (%)) ((numerator &&& denominator) . toRational) Memo.integral 

---

Another approach.

You have

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

How about you change this to

 step :: (V Double -> (V Double, V Double)) -> (V Double -> (V Double, V Double)) step hx = (r fx gx, s fx gx) where (fx, gx) = hx 

And also change

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

We hope that the common fx and gx should lead to acceleration.

Answer 2

Is there a way to remember this without breaking the entire program (for example, evaluating f0 and g0 with all the relevant arguments and then working up)?

It may be what you mean by “breaking the whole program”, but here is a solution in which (I believe, but cannot verify the ATM) fooX can be used together.

 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) 

I do not know if this preserves the spirit of your original implementation.