Partial memoization in Haskell

I'm trying to find a good way to memoize a function for only part of its domain (non-negative integers) in Haskell, using 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) +开发者_Python百科 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)

Approach 1 is how I would like to do it, however, it doesn't seem to work. I assume this is because the fib function is "recreated" every time partFib is called, throwing away the memoization. fib doesn't depend on the input of partFib, so you would assume that the compiler could hoist it, but apparently GHC doesn't work that way.

Approach 2 is how I end up doing it. Eerk, a lot of ugly wiring.

Does anybody know of a better way to do this?

Not quite sure what's "ugly" to your eye, but you can have proper memoization while using only a single top-level identifier by lifting the memoization operation out of the function of 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

Hmm what about separating things a bit:

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

Now you need to use doFib.

There is a combinator in the library for this purpose:

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

switch p a b uses the memo table a whenever p gives true and the memo table b whenever p gives false.

Recall that id is technically a memoizer (which does not memoize :-), so you can do:

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