メモ型の乗算

Question

私のアプリケーションは、FFTを使用して（高価な）変換の後にベクトルを乗算します。私は

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

を書くときその結果、私はむしろ、xsのすべての要素についてよりも、一度cのFFTを計算したいです。実際には、プログラム全体のFFTをcとしてローカルスコープに格納する必要はありません。

私は次のように私のNumインスタンスを定義しようとしました：そして、アプリケーションでは、私は（任意Numの上で動作します）fと同様の機能c=Vec False vを呼び出して、私はこれはと予想さ

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) 

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

機能gfft cのメモ化が起こりなり、ムーです：同じくらい速く、私はfにはハックかのようになりますどのように私が(*)を定義しても、fを呼び出すよりも速くなります。 fで何が問題になるのか分かりません。 Numインスタンスの私の定義は(*)ですか？ fがすべてのNumを扱うことと関係しているので、GHCは部分的に(*)を計算する方法を見つけることができませんか？

Note：Numインスタンスのコア出力をチェックしましたが、（*）は実際にネストされたラムダとして表され、最上位のラムダにFFT変換されています。それで、少なくともこれはメモに記入することができるようです。また、評価を強制的に無効にしようとするために、賢明で無謀なバングパターンの使用を試みました。私は(*)はその最初の引数をmemoize作成する方法を見つけ出すことができても、サイドノートとして

、それが定義されている方法で別の問題がまだある：使用したいプログラマは、Fooのデータ型が知っている必要がありこのメモ能力。彼女が書いた場合は、

map (*c) xs 

は発生しませんでした。 （(map (c*) xs))と書く必要があります。私は(*)をカレーして以来、GHCが(*c)バージョンをどのように書き換えるのかが完全にはわかりませんが、(*c)と(c*)の両方が期待通りに動作することを確認するためのクイックテストを行いました。 (c*)をcとすると、最初の引数は*になりますが、(*c)はcになります。*になります。 *への引数が対称であるという暗黙の前提）？

第2の重要な問題は、 スカラーのリストにマップ（v *）します。この場合、（おそらく）vのfftは、他の被乗数がスカラーなので不要であるとしても、計算されて格納されます。これを回避する方法はありますか？

おかげ

Answer 1

私はstable-memoパッケージで問題を解決できると考えています。ほとんどのメモコンビネータは平等、安定したメモをもとにmemoizeのに対し、それはつまり、（前にまったく同じ引数が関数に渡されているかどうかに基づいん

である：それは価値が平等を使用しますが、参照のアイデンティティではないmemoizesメモリ内の同じ引数）。

そして、それは自動的にそのキーがガベージコレクトされているメモ化値低下：

が安定し、メモは、彼らがする場合は、それらのゴミを収集することを可能にする、それがこれまで見てきたキーを保持しません。もはや使用されません。この場合、ファイナライザが配置されて対応するエントリがメモテーブルから削除されます。 (*)に最初の呼び出し内部のFFTの計算をmemoizeますmap (c *) xsを呼び出すと、それは以降の呼び出しで再利用されます：あなたは、かなりあなたが必要なものを買ってあげる

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

のようなものを定義している場合

(c *)。 cがガベージコレクションされている場合は、fft' cも同様です。

は-O2` `でコンパイルし、コンパイルされたコードでベンチマークもthis answerHow to add fields that only cache something to ADT?

Answer 2

私がメモ化を妨げる可能性の二つの問題を参照することができます

まず、fが過負荷のタイプがあり、すべてのNumインスタンスに対して動作します。したがってfは、特殊化（通常はSPECIALIZEプラグマが必要）またはインライン化（​​自動的に発生する可能性がありますが、INLINEプラグマではより信頼性が高い）でない限り、メモ化を使用できません。

Fooの(*)の定義では、最初の引数でパターンマッチングを実行しますが、fは未知数cを乗算します。従ってfの中で、専門化されていても、メモ化は起こりません。ここでも、fがインライン化されており、cの具体的な引数が提供されているため、実際にインライン展開が可能になります。

だから私はそれが正確にあなたがfと呼んでいるのを見るのを助けると思う。 fが2つの引数を使用して定義されている場合は、2つの引数を指定する必要があります。そうでない場合は、インライン化できません。さらに、Fooの実際の定義を見るのに役立ちます。あなたが与えているものはcとvで、範囲外です。