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

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?
• 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. :) May 21 '17 at 2:21
• @Jules actually that's the same link May 21 '17 at 2:32

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'
``````