Ghi lại đối số độc lập

Question

Tôi có mô phỏng với nhiều cuộc gọi đến các chức năng của type F = A -> B -> C -> D, trong đó A .. D là các loại cụ thể.

Các đối tượng thuộc loại A có tuổi thọ trung bình. (Đó là bộ gen của codegolf's ratrace.)

Tính toán đắt nhất phát sinh từ tham số A. Tôi có thể dễ dàng memoize như thế này:

f1 :: F 
f1 a = let expensive = trace "expensive computation!" $ expensiveComputation a 
     in \b c -> expensive 

và giữ một số tiền xử lý expensive giá trị thông qua ứng dụng phần:

preProz :: [B -> C -> D] 
preProz = [f1 [], f1 [False], f2 []] 

Các dấu vết cho thấy preProz <*> [[],[[]]] <*> [1,2] không recompute các giá trị để tôi ưa thích.

Bây giờ tôi đã phát hiện ra rằng một số trong số F của tôi cũng sẽ được hưởng lợi từ việc xử lý trước B. tiền xử lý này là độc lập từ A, và, trên thực tế, memoizing như thế này không có lợi ích

f2 a = let expensive = trace "expensive computation!" $ expensiveComputation a 
     in \b -> let dear = trace "expensive computation!" $ expensiveComputation b 
        in expensive + dear 

vì dear được tính toán lại, thậm chí là b s bằng nhau.

Những gì tôi cần là một cái gì đó như:

(B -> e) -> A -> e -> C -> D 

nơi e nên memoized. Loại e là loại tồn tại ở đây. Nhưng điều này buộc tôi phải tính lại tất cả các giá trị A cho mỗi B, điều này cũng không tốt, và tôi không thể lưu các số e s, riêng tư cho hàm.

Làm cách nào để ghi nhớ cùng 2 thông số một cách độc lập?

Answer 1

Bạn cần một chức năng mà memoizes cả a và b với nhau:

f12 a b = ... 
    in \c -> ... 

Khi bạn muốn memoize a nhưng không b, bạn sử dụng f1 a và khi bạn muốn memoize cả bạn sử dụng f12 a b.

Tất nhiên sẽ rất tuyệt khi chia sẻ một số triển khai giữa f1 và f12. Tuy nhiên, bạn có thể làm điều đó chỉ bằng cách có chức năng tin rằng lấy kết quả precomputed ở vị trí của giá trị ban đầu:

f1 a = privateA (precomputeA a) 
f12 a b = privateAB (precomputeA a) (precomputeB b) 
privateA a' b = privateAB a' (precomputeB b) 
private AB a' b' c = ... 

Nếu tính toán trước của b phụ thuộc vào tính toán trước của a, sau đó:

f1 a = privateA (precomputeA a) 
f12 a b = let a' = precomputeA a in privateAB a' (precomputeB a' b) 
privateA a' b = privateAB a' (precomputeB a' b) 
private AB a' b' c = ... 

Tôi đã cố tình không sử dụng thành phần chức năng và giảm eta, để làm cho mọi việc rõ ràng hơn. Tôi cũng đã loại bỏ bất kỳ chú thích nghiêm ngặt nào mà bạn có thể muốn sử dụng để kiểm soát thời gian đánh giá.

Có lẽ việc ghi nhớ không hoàn toàn đúng thời hạn ở đây.Bạn có nghĩa là một cái gì đó giống như "một phần ứng dụng với một số precomputation là tốt."