Ghi nhớ một phần trong Haskell

Question

Tôi đang cố gắng tìm một cách tốt để ghi nhớ một chức năng chỉ cho một phần của miền (số nguyên không âm) trong Haskell, sử dụng 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) 

Phương pháp tiếp cận 1 là cách tôi muốn thực hiện, tuy nhiên, dường như nó không hoạt động. Tôi cho rằng điều này là do hàm fib được "tạo lại" mỗi khi partFib được gọi, bỏ đi việc ghi nhớ. fib không phụ thuộc vào đầu vào của partFib, vì vậy bạn sẽ giả định rằng trình biên dịch có thể hoist nó, nhưng dường như GHC không hoạt động theo cách đó.

Cách tiếp cận 2 là cách tôi kết thúc. Eerk, rất nhiều hệ thống dây điện xấu xí.

Có ai biết cách nào tốt hơn để làm điều này không?

Answer 1

Không chắc chắn về những gì "xấu xí" đối với mắt của bạn, nhưng bạn có thể ghi nhớ thích hợp khi chỉ sử dụng một mã định danh cấp cao nhất bằng cách nâng hoạt động ghi nhớ ra khỏi chức năng 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 gì về tách thứ một chút:

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 

Bây giờ bạn cần phải sử dụng doFib.

Answer 3

Có một combinator trong thư viện cho mục đích này:

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

switch p a b sử dụng bảng ghi nhớ a bất cứ khi nào p cho đúng và bảng ghi nhớ b bất cứ khi nào p cho sai.

Nhớ lại rằng id là một kỹ thuật memoizer (mà không memoize :-), vì vậy bạn có thể làm:

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