Memoization với đệ quy

Question

Tôi cố gắng để hiểu Haskell realization of memoization, nhưng tôi không nhận được cách thức hoạt động:

memoized_fib :: Int -> Integer 
memoized_fib = (map fib [0..] !!) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1) 

Trước hết tôi thậm chí còn không hiểu tại sao 'map' chức năng nhận được ba thông số (chức năng - fib, danh sách [0 ..], và ||), nhưng không phải là hai cách nó phải làm.

Cập nhật:

tôi đã cố gắng viết lại mã, nhưng có được kết quả khác nhau:

f' :: (Int -> Int) -> Int -> Int 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Int] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Int -> Int 
faster_f' n = f'_list !! n 

Tại sao? Có bất kỳ lỗi nào trong lý luận của tôi không?

Answer 1

Đầu tiên: Haskell hỗ trợ các toán tử. Vì vậy, (+ 2) bằng \ x -> x + 2. Điều này có nghĩa là biểu thức với map bằng \ x -> map fib [0..] !! x.

Thứ hai, cách thức hoạt động: điều này đang tận dụng lợi thế của chiến lược đánh giá call-by-need của Haskell (sự lười biếng của nó).

Ban đầu, danh sách kết quả từ số map không được đánh giá. Sau đó, khi bạn cần phải nhận được một số chỉ số cụ thể, tất cả các yếu tố cho đến thời điểm đó được đánh giá. Tuy nhiên, khi một phần tử được đánh giá, nó không được đánh giá lại (miễn là bạn đang đề cập đến cùng một phần tử). Đây là những gì mang lại cho bạn sự ghi nhớ.

Về cơ bản, chiến lược đánh giá lười biếng của Haskell liên quan đến việc ghi nhớ các giá trị bắt buộc. Chức năng fib được ghi nhớ này chỉ dựa vào hành vi đó.

Ở đây "buộc" giá trị có nghĩa là đánh giá biểu thức trì hoãn được gọi là một đoạn. Vì vậy, danh sách về cơ bản ban đầu được lưu trữ như là một "lời hứa" của một danh sách, và buộc nó biến "lời hứa" thành một giá trị thực tế, và một "lời hứa" cho nhiều giá trị hơn. Những "lời hứa" chỉ là những người thân, nhưng tôi hy vọng việc gọi đó là một lời hứa có ý nghĩa hơn.

Tôi đang đơn giản hóa một chút, nhưng điều này sẽ làm rõ cách hoạt động của tính năng ghi nhớ thực tế.

Answer 2

map không lấy ba tham số ở đây.

(map fib [0..] !!) 

phần áp dụng (lát) chức năng (!!) với map fib [0..], một danh sách, như đầu tiên (bên trái) đối số của nó.

Answer 3

Có thể đó là rõ ràng bằng văn bản nó như:

memoized_fib n = (map fib [0..]) !! n 

vì vậy nó chỉ lấy yếu tố thứ n từ danh sách, và danh sách được đánh giá một cách lười biếng.

Công cụ operator section này chính xác giống như ứng dụng một phần thông thường, nhưng đối với các nhà khai thác infix. Trong thực tế, nếu chúng ta viết các hình thức tương tự với một chức năng thường xuyên thay cho nhà điều hành ghi !!, xem làm thế nào nó trông giống:

import Data.List (genericIndex) 

memoized_fib :: Int -> Integer 
memoized_fib = genericIndex (map fib [0..]) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1)