10

我的应用程序在使用 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（适用于任意Nums） where的函数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处理所有 Nums 有关，因此 GHC 无法弄清楚如何部分计算(*)？

注意：我检查了我的 Num 实例的核心输出，并且 (*) 确实表示为嵌套 lambda，在顶层 lambda 中进行了 FFT 转换。所以看起来这至少可以被记忆。我还尝试过明智地和鲁莽地使用 bang 模式来试图强制评估无效。

附带说明一下，即使我能弄清楚如何让(*)memoize 成为它的第一个参数，它的定义方式还有另一个问题：想要使用Foo 数据类型的程序员必须了解这种 memoize 功能。如果她写

map (*c) xs

不会发生记忆。（它必须写成(map (c*) xs))现在我想起来了，我不完全确定 GHC 将如何重写(*c)版本，因为我已经 curried (*)。但我做了一个快速测试来验证两者(*c)并按(c*)预期工作：(c*)将c第一个 arg 设为*, 而(*c)将c第二个 arg 设为*. 所以问题在于如何编写乘法以确保记忆并不明显. 这只是中缀符号的固有缺点（以及参数*是对称的隐含假设）吗？

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

谢谢

4

2 回答 2

2

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

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

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

stable-memo 不会保留它迄今为止看到的密钥，如果它们不再被使用，这将允许它们被垃圾收集。如果发生这种情况，将放置终结器以从备忘录表中删除相应的条目。

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

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

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

另请参阅如何添加仅将某些内容缓存到 ADT 的字段的答案？

于 2013-02-26T08:11:24.093 回答
1

我可以看到两个可能会阻止记忆的问题：

首先，f具有重载类型并适用于所有Num实例。所以f不能使用 memoization，除非它是专门的（通常需要一个SPECIALIZEpragma）或内联的（这可能会自动发生，但使用 pragma 更可靠INLINE）。

其次， for 的定义(*)对Foo第一个参数执行模式匹配，但f与 unknown 相乘c。所以在 内f，即使是专门的，也不会发生记忆。再一次，它在很大程度上取决于f被内联，并提供一个具体的参数c，这样内联才能真正出现。

所以我认为看看你打电话的准确程度会有所帮助f。请注意，如果f使用两个参数定义，则必须给它两个参数，否则不能内联。此外，查看 的实际定义会有所帮助Foo，因为您提到的c定义v不在范围内。

于 2013-02-26T07:57:48.253 回答