Memoizing乘法

Question

我的應用程序使用FFT一個（昂貴的）變換後乘以向量。其結果是，當我寫

f :: (Num a) => a -> [a] -> [a] 
f c xs = map (c*) xs 

我只是想計算的c的FFT一次，而不是爲xs每個元素。實際上沒有必要爲整個程序存儲c的FFT，只是在本地範圍內。

我試圖像來定義我的Num例如：

data Foo = Scalar c 
     | Vec Bool v -- the bool indicates which domain v is in 

instance Num Foo where 
    (*) (Scalar c) = \x -> case x of 
         Scalar d -> Scalar (c*d) 
         Vec b v-> Vec b $ map (c*) v 
    (*) v1 = let Vec True v = fft v1 
      in \x -> case x of 
        Scalar d -> Vec True $ map (c*) v 
        v2 -> Vec True $ zipWith (*) v (fft v2) 

然後，在一個應用程序，我稱之爲類似於f（其上的任意Num作品），其中c=Vec False v一個功能，我預期這將是一樣快，如果我砍f到：

g :: Foo -> [Foo] -> [Foo] 
g c xs = let c' = fft c 
     in map (c'*) xs 

功能g使fft c發生的記憶化，並萬畝比呼叫f快（不管我如何定義(*)）。我不明白f出了什麼問題。 Num實例中是否是我對(*)的定義？它有事情做與工作f對所有訂購數量，因此GHC暫時無法弄清楚如何計算部分(*)？

注意：我檢查了我的Num實例的核心輸出，並且（*）的確表示爲頂層lambda中FFT轉換的嵌套lambdas。所以看起來這至少能夠被記憶。我也嘗試了謹慎和魯莽地使用爆炸模式，試圖迫使評估毫無效果。

作爲一個側面說明，即使我可以計算出如何使(*) memoize的第一個參數，還有它是如何定義的另一個問題：一個程序員想要使用的富數據類型有了解這種記憶能力。如果她寫了

map (*c) xs 

不會發生記憶。 （它必須寫成(map (c*) xs))現在我想到了，我不完全確定GHC如何重寫(*c)版本，因爲我已經嘗試過(*)但我做了一個快速測試，以驗證(*c)和(c*)都按預期工作： (c*)使c第一個參數爲*，而(*c)使c第二個參數爲*。所以問題在於如何寫乘法來確保記憶是不明顯的。這是否是中綴記號的固有缺點（和隱含的假設參數*是對稱的）？

第二，那麼緊迫的問題是，情況WHE我們再映射（V *）到的標量列表。在這種情況下，（希望）v的fft將被計算和存儲，儘管由於另一個被乘數是標量是沒有必要的。有沒有辦法解決？

感謝

Answer 1

我相信stable-memo包可以解決您的問題。它memoizes不使用平等的，但通過參考標識值：

儘管大多數備忘錄組合子memoize的平等，穩定備忘錄它基於完全相同的參數是否已經傳遞給函數之前（即是內存中的同一個參數）。

當他們的密鑰是垃圾回收便會自動memoized值：

穩定備忘錄不保留到目前爲止，它已經看到了按鍵，這使得他們能夠被垃圾收集，如果他們將不再使用。如果發生這種情況，終結器將在備忘錄表中刪除相應的條目。

所以，如果你定義像

fft = memo fft' 
    where fft' = ... -- your old definition 

你會得到相當多你所需要的：調用map (c *) xs將第一調用內部的FFT計算memoize的到(*)連帶在後續調用重用到(c *)。如果c是垃圾回收，fft' c也是。

參見this answer到How to add fields that only cache something to ADT?

Answer 2

我可以看到兩個問題可能會阻礙記憶化：

首先，f一個重載的類型和適用於所有Num實例。因此f不能使用記憶，除非它是專門的（通常需要SPECIALIZE編譯指示）或內聯（可能會自動發生，但用INLINE編譯指示更可靠）。

其次，Foo的(*)的定義在第一個參數上執行模式匹配，但f乘以未知的c。因此，在f內，即使專門化，也不會發生記憶。再一次，它非常依賴f被內聯，並提供了一個c的具體參數，以便內聯實際上可以出現。

所以我認爲這會有助於看到你打電話的方式f。請注意，如果f是使用兩個參數定義的，則必須給它兩個參數，否則它不能被內聯。它還有助於看到Foo的實際定義，因爲您提到的不是範圍內的c和v。