記憶類型爲（）的函數 - >'a

This memoize function在運行時帶有空參數異常的任何類型爲() -> 'a的函數都會失敗。記憶類型爲（）的函數 - >'a

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

有沒有辦法寫一個記憶功能，也適用於() -> 'a？

（我唯一的選擇，現在是使用Lazy類型。調用x.Force()得到的數值。）（太不只是unit -> 'a型的，但任何其他），具有純函數

來源

2013-12-12 Goswin

Memoize通常用於在參數用作查找鍵的參數上緩存一些計算。在這種情況下，「懶惰」是正確的工具。 – Daniel

你可以用'lazy'來包裝，例如：'let memoize f = let result = lazy（f（））in fun（） - > result.Value' – Daniel

函數失敗的原因是F＃代表使用unit類型的null的單元()。字典不允許將null作爲鍵值，因此失敗。

在特定情況下，是不是在unit -> 'a型memoizing功能多點（因爲它是更好地使用lazy此），但也有其他情況下，這將是一個問題 - 例如None也代表通過null所以這也失敗：

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

最簡單的辦法來解決，這是包裝的關鍵在另一個數據類型，以確保它永遠不會null：

type Key<'K> = K of 'K

然後，你可以換用K構造的關鍵，一切都會很好地工作：

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

來源

2013-12-12 18:29:36

不應該是'Dictionary（HashIdentity.Structural）？ – Daniel

是不是它爲通過調用'memoize'定義的每個函數創建了一個'cache'字典的自己的實例？僅僅因爲這個多個鍵'K '可能存在'unit - >'a'而沒有衝突。由於函數不共享公共緩存，因此任何文字都可能扮演密鑰的角色，整個安排有效地模仿「懶惰」的方法。 –

@Gene memoize返回一個關閉它自己的Dictionary實例的函數。 memoize的簽名是 '˚F:('一 - > 'B） - >（' 一個 - >' b）如果 'A：equality' 以便它返回該函數是 '' 一 - >「B ' 這是您用於記憶值的返回函數。例如， 'let m = memoize（fun x - > x + 1）;;' 給出 'val m：（int - > int）' –

記憶化作爲查找鍵因爲一般的功能不具備reason的等號比較器。

看起來對於這種特定類型的函數unit -> 'a，可能會出現一個自定義的相等比較器。但是，實現這種比較器超出極限（反射，IL等）的唯一方法將是調用查找函數爲f1 = f2 iff f1() = f2()，這顯然使記憶化期望的任何性能改進無效。

因此，也許正如已經提到的那樣，對於這種情況，優化應該建立在lazy模式的周圍，而不是memoization之一。

更新：事實上，在第二次查看這個問題之後，所有上面關於函數缺少的相等比較器的說法都是正確的，但不適用，因爲memoization在閉包中的每個函數的個體cache內發生。另一方面，對於具有簽名unit->'a的這種特定類型的功能，即最多單個參數值，使用Dictionary以及最多一個條目是過度殺傷。下面同樣有狀態的，但更簡單的實現只用一個memoized值會做：

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

用作let foo = memoize2(fun() -> ...heavy on time and/or space calculation...) 與第一次使用foo()執行並存儲計算結果和所有連續foo()只是重新使用存儲的值。

來源

2013-12-12 18:21:52

我剛剛發現最後memoize的功能on the same website使用Map代替Dictionary作品'a Option -> 'b和() -> 'a太：

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

來源

2013-12-13 14:02:15 Goswin

-1

帶有可變字典和單字典查詢調用的解決方案： 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

來源

2016-08-12 13:27:04

這並不能解決問題中提出的問題。 'memoize1（fun（） - > 1）（）'也因'ArgumentNullException'失敗，出於同樣的原因。 – kvb

記憶類型爲（）的函數 - >'a

回答

相關問題