Làm thế nào để bạn thực hiện một chức năng ghi nhớ chung trong Haskell?

Question

Tôi đã xem the other post about this, nhưng có cách nào để làm điều này trong Haskell không?

Là phần thứ hai, nó có thể được thực hiện mà không cần thực hiện chức năng đơn thuần không?

Answer 1

Phần lớn này theo sau http://www.haskell.org/haskellwiki/Memoization.

Bạn muốn có chức năng loại (a -> b). Nếu nó không tự gọi, thì bạn chỉ có thể viết một trình bao bọc đơn giản để lưu trữ các giá trị trả về. cách tốt nhất để lưu trữ ánh xạ này phụ thuộc vào thuộc tính nào của bạn có thể khai thác . Đặt hàng là khá nhiều tối thiểu. Với số nguyên , bạn có thể tạo danh sách lười vô hạn hoặc cây giữ các giá trị.

type Cacher a b = (a -> b) -> a -> b 

positive_list_cacher :: Cacher Int b 
positive_list_cacher f n = (map f [0..]) !! n 

hoặc

integer_list_cacher :: Cacher Int b 
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !! 
    index n where 
     index n | n < 0 = 2*abs(n) - 1 
     index n | n >= 0 = 2 * n 

Vì vậy, giả sử nó là đệ quy. Sau đó, bạn cần nó để gọi không chính nó, nhưng phiên bản memoized, vì vậy bạn vượt qua rằng trong thay vì:

f_with_memo :: (a -> b) -> a -> b 
f_with_memo memoed base = base_answer 
f_with_memo memoed arg = calc (memoed (simpler arg)) 

Phiên bản memoized là, tất nhiên, những gì chúng tôi đang cố gắng để xác định.

Nhưng chúng ta có thể bắt đầu bằng cách tạo ra một chức năng lưu trữ nguyên liệu đầu vào của nó:

Chúng ta có thể xây dựng một mức độ bằng cách đi qua trong một chức năng mà tạo ra một cấu trúc rằng lưu trữ giá trị. . Ngoại trừ chúng ta cần phải tạo ra các phiên bản của f rằng đã có chức năng lưu trữ thông qua vào

Nhờ sự lười biếng, đây là không có vấn đề:

memoize cacher f = cached where 
     cached = cacher (f cached) 

sau đó tất cả chúng ta cần là để sử dụng nó:

exposed_f = memoize cacher_for_f f 

bài viết này cung cấp cho những gợi ý như thế nào để sử dụng một lựa chọn kiểu lớp trên đầu vào cho các chức năng để làm các việc trên, thay vì chọn mộtrõ ràngchức năng bộ nhớ đệm. Điều này có thể thực sự tốt đẹp - thay vì rõ ràng xây dựng bộ nhớ cache cho từng kết hợp loại đầu vào, chúng tôi hoàn toàn có thể kết hợp các bộ đệm a và b vào bộ đệm cho một hàm lấy a và b.

Thông báo cuối cùng: sử dụng kỹ thuật lười biếng này có nghĩa là bộ nhớ cache không bao giờ co lại, chỉ phát triển. Thay vào đó, nếu bạn sử dụng trình đơn IO, bạn có thể quản lý điều này, nhưng làm điều đó một cách khôn ngoan phụ thuộc vào các mẫu sử dụng.

Answer 2

Nếu lập luận của bạn sẽ được các số tự nhiên, bạn có thể làm đơn giản:

memo f = let values = map f [0..] 
    in \n -> values !! n 

Tuy nhiên, điều đó không thực sự giúp bạn ngăn xếp tràn, và nó không hoạt động với các cuộc gọi đệ quy. Bạn có thể thấy một số giải pháp fancier tại http://www.haskell.org/haskellwiki/Memoization.

Answer 3

Làm bản dịch trực tiếp từ các ngôn ngữ bắt buộc hơn, tôi đã nghĩ ra điều này.

memoize :: Ord a => (a -> IO b) -> IO (a -> IO b) 
memoize f = 
    do r <- newIORef Map.empty 
    return $ \x -> do m <- readIORef r 
         case Map.lookup x m of 
          Just y -> return y 
          Nothing -> do y <- f x 
              writeIORef r (Map.insert x y m) 
              return y 

Nhưng điều này bằng cách nào đó không đạt yêu cầu. Ngoài ra, Data.Map ràng buộc tham số là một phiên bản của Ord.

Answer 4

Các gói dữ liệu-memocombinators về hackage cung cấp rất nhiều thói quen ghi nhớ tái sử dụng. Ý tưởng cơ bản là:

type Memo a = forall r. (a -> r) -> (a -> r) 

I.e. nó có thể ghi nhớ bất kỳ hàm nào từ a. Mô-đun này sau đó cung cấp một số nguyên thủy (như unit :: Memo() và integral :: Memo Int) và các bộ phối hợp để xây dựng các bảng ghi nhớ phức tạp hơn (như pair :: Memo a -> Memo b -> Memo (a,b) và list :: Memo a -> Memo [a]).

Answer 5

Bạn có thể sửa đổi giải pháp của Jonathan bằng unsafePerformIO để tạo phiên bản ghi nhớ "thuần túy" của hàm của bạn.

import qualified Data.Map as Map 
import Data.IORef 
import System.IO.Unsafe 

memoize :: Ord a => (a -> b) -> (a -> b) 
memoize f = unsafePerformIO $ do 
    r <- newIORef Map.empty 
    return $ \ x -> unsafePerformIO $ do 
     m <- readIORef r 
     case Map.lookup x m of 
      Just y -> return y 
      Nothing -> do 
        let y = f x 
        writeIORef r (Map.insert x y m) 
        return y 

này sẽ làm việc với chức năng đệ quy:

fib :: Int -> Integer 
fib 0 = 1 
fib 1 = 1 
fib n = fib_memo (n-1) + fib_memo (n-2) 

fib_memo :: Int -> Integer 
fib_memo = memoize fib 

Altough ví dụ này là một hàm với một tham số số nguyên, loại memoize cho chúng ta biết rằng nó có thể được sử dụng với bất kỳ chức năng mà phải mất một so sánh kiểu. Nếu bạn có một hàm có nhiều hơn một tham số, hãy nhóm chúng lại thành một bộ tuple trước khi áp dụng ghi nhớ. F.i .:

f :: String -> [Int] -> Float 
f ... 

f_memo = curry (memoize (uncurry f))