Ghi nhớ chức năng loại() -> 'a

Question

This memoize function không thành công trên bất kỳ chức năng nào của loại () -> 'a khi chạy với ngoại lệ Null-Argument-Exception.

let memoize f = 
    let cache = System.Collections.Generic.Dictionary() 
    fun x -> 
     if cache.ContainsKey(x) then 
      cache.[x] 
     else 
      let res = f x 
      cache.[x] <- res 
      res 

Có cách nào để viết chức năng ghi nhớ cũng hoạt động cho () -> 'a không?

(lựa chọn duy nhất của tôi bây giờ đang sử dụng một loại Lazy. Gọi x.Force() để lấy giá trị.)

Answer 1

Lý do tại sao hàm không thành công là F # đại diện cho đơn vị () sử dụng null loại unit. Từ điển không cho phép lấy các giá trị null làm khóa và do đó không thành công.

Trong trường hợp cụ thể của bạn, không có nhiều điểm trong chức năng ghi nhớ loại unit -> 'a (vì tốt hơn là sử dụng lazy cho điều này), nhưng có những trường hợp khác, đây là vấn đề - ví dụ: None bởi null vì vậy đây không quá:

let f : int option -> int = memoize (fun a -> defaultArg a 42) 
f None 

cách đơn giản để khắc phục điều này là để bọc chìa khóa trong một loại dữ liệu để đảm bảo nó không bao giờ là null:

type Key<'K> = K of 'K 

Sau đó, bạn chỉ có thể quấn phím với các nhà xây dựng K và tất cả mọi thứ sẽ làm việc độc đáo:

let memoize f = 
    let cache = System.Collections.Generic.Dictionary() 
    fun x -> 
     if cache.ContainsKey(K x) then 
      cache.[K x] 
     else 
      let res = f x 
      cache.[K x] <- res 
      res 

Answer 2

Memoization có một chức năng thuần túy (không chỉ là loại unit -> 'a, nhưng bất kỳ khác quá) như một chìa khóa tra cứu là không thể bởi vì các hàm nói chung không có sự so sánh bình đẳng cho reason.

Dường như đối với loại chức năng cụ thể này unit -> 'a, có thể sẽ có một bộ so sánh bình đẳng tùy chỉnh. Nhưng cách tiếp cận duy nhất để thực hiện so sánh đó vượt quá thái cực (phản ánh, IL, v.v.) sẽ là gọi hàm tra cứu là f1 = f2 iff f1() = f2(), điều này dường như vô hiệu hóa bất kỳ cải thiện hiệu suất nào được mong đợi từ việc ghi nhớ.

Vì vậy, có lẽ, như đã được lưu ý, trong trường hợp này, tối ưu hóa nên được xây dựng xung quanh mẫu lazy, nhưng không phải là memoization.

CẬP NHẬT: Thật vậy, sau khi nhìn vào câu hỏi, tất cả đều nói về các hàm thiếu so sánh bình đẳng là chính xác, nhưng không áp dụng được, vì memoization xảy ra trong từng trường hợp riêng lẻ của từng chức năng cache. Ở phía bên kia, đối với loại hàm cụ thể này có chữ ký unit->'a, tức là tại hầu hết giá trị của đối số, sử dụng Dictionary với hầu hết một mục nhập là quá mức cần thiết. sau khi thực hiện tương tự như trạng thái, nhưng đơn giản chỉ với một giá trị memoized sẽ làm:

let memoize2 f = 
    let notFilled = ref true 
    let cache = ref Unchecked.defaultof<'a> 
    fun() -> 
     if !notFilled then 
      cache := f() 
      notFilled := false 
     !cache 

sử dụng như let foo = memoize2(fun() -> ...heavy on time and/or space calculation...) với việc sử dụng đầu tiên foo() thực hiện và lưu trữ các kết quả tính toán và tất cả liên tiếp foo() chỉ tái sử dụng các giá trị được lưu trữ.

Answer 3

Tôi chỉ thấy rằng chức năng memoize cuối cùng on the same website sử dụng Map thay vì Dictionary công trình cho 'a Option -> 'b và () -> 'a quá:

let memoize1 f = 
    let cache = ref Map.empty 
    fun x -> 
     match (!cache).TryFind(x) with 
     | Some res -> res 
     | None -> 
      let res = f x 
      cache := (!cache).Add(x,res) 
      res 

Answer 4

Giải pháp với từ điển có thể thay đổi và tra cứu từ điển đơn lẻ: let memoize1 f = // printfn "Dictionary" let cache = System.Collections.Generic.Dictionary() fun x -> let result, value = cache.TryGetValue(x) match result with | true -> value | false -> // printfn "f x" let res = f x cache.Add(x, res) res