Memorización parcial en Haskell

Question

Estoy tratando de encontrar una buena manera de memorizar una función para solo una parte de su dominio (enteros no negativos) en Haskell, usando 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) 

Enfoque 1 es cómo me gustaría hacerlo, sin embargo, parece que no funciona. Supongo que esto se debe a que la función fib se "recrea" cada vez que se invoca partFib, descartando la memorización. fib no depende de la entrada de partFib, por lo que podría suponer que el compilador podría izarlo, pero aparentemente GHC no funciona de esa manera.

Enfoque 2 es cómo termino haciéndolo. Eerk, muchos cables feos.

¿Alguien sabe de una mejor manera de hacer esto?

Answer 1

No estoy seguro de lo que es "feo" para su ojo, pero puede memorizar correctamente mientras usa solo un identificador de nivel superior al sacar la operación de memoria de la función 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 lo de separar un poco las cosas:

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 

Ahora tiene que utilizar doFib.

Answer 3

No es un combinador en la biblioteca para este propósito:

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

switch p a b utiliza la tabla de notas a siempre p da verdadera y la tabla de notas b siempre p da falsa.

Recordemos que id es técnicamente un memoizer (que no memoize :-), por lo que puede hacer:

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