记忆乘法

Question

我的应用程序在使用FFT进行(昂贵)转换后将向量相乘.结果,当我写作

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

我只想计算c一次FFT ,而不是计算每个元素的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(在任意Nums上工作)的函数c=Vec False v,并且我预计这会像我讨厌的那样快f:

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

该函数g使得memoization fft c发生,并且比调用快得多f(无论我如何定义(*)).我不明白出了什么问题f.这是我(*)在Num实例中的定义吗？它是否与f处理所有Nums有关,因此GHC无法弄清楚如何部分计算(*)？

注意:我检查了Num实例的核心输出,并且(*)确实表示为嵌套的lambdas,顶层lambda中的FFT转换.所以看起来这至少能够被记忆.我也尝试过明智和鲁莽地使用爆炸模式来试图强制评估无效.

作为旁注,即使我可以弄清楚如何(*)对它的第一个参数进行memoize,还有另一个问题就是如何定义:想要使用 Foo数据类型的程序员必须知道这个memoization功能.如果她写的

map (*c) xs

不会发生任何记忆.(它必须写成(map (c*) xs))现在,我想到它,我不完全确定GHC将如何重写该(*c)版本,因为我已经咖喱(*).但我做了一个快速测试,以验证两者(*c)并按(c*)预期工作:(c*)使c第一个arg到*,而(*c)使得c第二对Arg的*,所以问题是,它不是明显的应该怎么写乘法,以确保记忆化.这只是一个固有的缺点中缀表示法(和隐含的假设参数*是对称的)？

第二个不太紧迫的问题是我们将(v*)映射到标量列表的情况.在这种情况下,(希望)v的fft将被计算和存储,即使它是不必要的,因为另一个被乘数是标量.有没有办法解决？

谢谢

Answer 1

我相信stable-memo包可以解决你的问题。它不使用相等性而是通过引用标识来记忆值：

大多数备忘录组合器基于相等性进行记忆，而 stable-memo 则根据之前是否已将完全相同的参数传递给函数（即内存中的相同参数）来进行记忆。

当键被垃圾收集时，它会自动删除记忆值：

stable-memo 不会保留迄今为止所看到的键，这使得它们在不再使用时可以被垃圾回收。如果发生这种情况，将设置终结器以从备忘录表中删除相应的条目。

所以如果你定义类似的东西

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

你会得到几乎你需要的东西：调用map (c *) xs将记住第一次调用中的 fft 计算(*)，并且它会在后续调用中重用(c *)。如果c被垃圾收集，那么fft' c.

另请参阅How to add fields that onlycache some to ADT? 的答案