Memoization in case of recursive interdefined functions in Haskell/Functional Programming?

Question

I was reading Memoization with recursion which tells how for a recursively defined function fun we can do memoization by:

-- Memoization
memoize f = (map f [0 ..] !!)
-- Base cases
g f 0 = 0
g f 1 = 1
-- Recursive Definition
g f n = f (n-1) + f (n-2)
-- Memoized Function
gMemo = fix (memoize . g)

So I think it is something like this:

gMemo = fix (memoize . g)
 = memoize (g . gMemo)
 = memoize (g . memoize (g . memoize ... memoize (g . gMemo)...)) 

Therefore it will recurse until it will find a value where memoize can get it's value or a base case, isn't it?

Now I am trying to define some functions which are interdependent, i.e.

-- P(0) = 0, d = 170, Q(0) = 1
-- alpha(k) = (P(k) + sqrt(n)) / Q(k)
-- a(k) = floor(alpha(k))
-- P(k+1) = a(k)Q(k)-P(k)
-- Q(k+1) = (d-P^2(k+1))/Q(k)

Now the above memoization for g includes an anonymous variable f, but here we would like specific functions.

My question is:

• Can someone clear how gMemo works, am I right?
• How can we make something like that work for P,Q,.. or something else?

• Jules: There's a good breakdown of how the code that you've got there (with some names changed but otherwise identical) works at wiki.haskell.org/Memoization. The article also provides some other mechanisms; I'd suggest using one of the variants that don't use a fixed point operator, primarily because fixed point operators really mess with my ability to understand code. :)
• RE60K: @Jules actually that's the same link

Answer 1

I came up with something like a state:

d' = sqrt $ fromIntegral 170
state = (map state' [0..] !!)
-- state = (p, q, a)
state' 0 = (0, 1, floor d')
state' k = (p', q', a')
 where
 (p, q, a) = state (k-1)
 alpha' = (fromIntegral p' + d') / fromIntegral q'
 p' = a * q - p
 q' = (n - p' * p') `div` q
 a' = floor alpha'