Частичная памятка в Хаскеле

Question

Я пытаюсь найти хороший способ запомнить функцию только для части ее домена (неотрицательные целые числа) в Haskell, используя 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)

Подход 1 - это то, как я хотел бы это сделать, однако, похоже, он не работает. Я предполагаю, что это потому, что функция fib «воссоздается» каждый раз, когда вызывается partFib, отбрасывая памятку. fib не зависит от ввода partFib, поэтому можно предположить, что компилятор может его поднять, но, очевидно, GHC не работает таким образом.

Подход 2 - вот как я это делаю. Черт, много отвратительной проводки.

Кто-нибудь знает лучший способ сделать это?

Answer 1

Не совсем уверен, что "некрасиво" на ваш взгляд, но вы можете иметь надлежащую памятку, используя только один идентификатор верхнего уровня, исключив операцию памятки из функции 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

Для этой цели в библиотеке есть комбинатор:

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

switch p a b использует таблицу напоминаний a всякий раз, когда p дает значение true, и таблицу заметок b всякий раз, когдаp дает ложь.

Напомним, что id технически является памятником (который не запоминает :-), так что вы можете сделать:

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

Answer 3

Хм, как насчет разделения вещей:

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

Теперь вам нужно использовать doFib.