Częściowa notacja w Haskell

Question

Próbuję znaleźć dobry sposób na zapamiętanie funkcji tylko dla części jej domeny (nieujemnych liczb całkowitych) w Haskell, używając Data.MemoCombinators.

import Data.MemoCombinators 

--approach 1 

partFib n | n < 0 = undefined 
      | otherwise = integral fib n where 
    fib 0 = 1 
    fib 1 = 1 
    fib k = partFib (k-1) + partFib (k-2) 

--approach 2 

partFib2 n | n < 0 = undefined 
      | otherwise = fib n 
fib = integral fib' 
    where 
    fib' 0 = 1 
    fib' 1 = 1 
    fib' n = partFib2 (n-1) + partFib2 (n-2) 

Podejście 1 to sposób, w jaki chciałbym to zrobić, ale wydaje się, że nie działa. Zakładam, że dzieje się tak dlatego, że funkcja fib jest "odtwarzana" za każdym razem, gdy wywoływana jest nazwa partFib, odrzucając tę ​​funkcję. fib nie zależy od wejścia partFib, więc można założyć, że kompilator może go podnieść, ale najwyraźniej GHC nie działa w ten sposób.

Podejście 2 to sposób, w jaki to robię. Eerk, dużo brzydkiego okablowania.

Czy ktoś wie o lepszy sposób to zrobić?

Answer 1

Nie jestem do końca pewien, co jest "brzydkie" dla oczu, ale możesz mieć prawidłową pamięć podczas używania tylko jednego identyfikatora najwyższego poziomu, odsuwając operację zapamiętywania z funkcji n.

partFib3 = \n -> if n < 0 then undefined else fib' n 
    where fib 0 = 1 
      fib 1 = 1 
      fib k = partFib3 (k-1) + partFib3 (k-2) 
      fib' = integral fib 

Answer 2

Hmm co oddzielania rzeczy trochę:

fib 0 = 0 
fib 1 = 1 
fib x = doFib (x-1) + doFib (x-2) 

memFib = Memo.integral fib 

doFib n | n < 0 = fib n 
     | otherwise memFib n 

Teraz trzeba użyć doFib.

Answer 3

Jest syntezatora w bibliotece do tego celu:

switch :: (a -> Bool) -> Memo a -> Memo a -> Memo a 

switch p a b używa tabeli notatki a ilekroć p daje prawdziwe i tablica memo b ilekroć p daje fałszywe.

Przypomnijmy, że id jest technicznie memoizer (co nie memoize :-), więc można zrobić:

partFib = Memo.switch (< 0) id Memo.integral fib' 
    where 
    ...