Memoizzazione in caso di funzioni interdefined ricorsive in Haskell / Programmazione funzionale?

Question

Memoizzazione in caso di funzioni interdefined ricorsive in Haskell / Programmazione funzionale?

#1 da (0 voti)

0

Stavo leggendo Memoization with recursion che indica come per una funzione definita in modo ricorsivo fun possiamo eseguire la memoizzazione di:

-- 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)

Quindi penso che sia qualcosa del genere:

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

Quindi reciterà fino a quando non troverà un valore in cui memoize può ottenere il suo valore o un caso base, non è vero?

Ora sto cercando di definire alcune funzioni che sono interdipendenti, cioè

-- 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)

Ora la precedente memoizzazione per g include una variabile anonima f, ma qui vorremmo funzioni specifiche.

La mia domanda è:

Qualcuno può chiarire come funziona gMemo , ho ragione?
Come possiamo far funzionare qualcosa del genere per P,Q,.. o qualcos'altro?

recursion functional-programming haskell math caching

posta RE60K 20.05.2017 - 18:01

fonte

1 risposta

Leggi altre domande sui tag recursion functional-programming haskell math caching

Gestione di un indice di metadati di file su una condivisione di rete MVVM / Xamarin che implementa servizi che richiedono altri servizi

score 0 · Accepted Answer

Mi è venuto in mente qualcosa di simile a uno stato:

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'