0

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

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'

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.