class - 如何使用 Data.Function.Memoize 的类方法？

Question

我正在处理 NP 搜索问题，有人告诉我可以使用 said 加快搜索过程包裹。由于内存对我来说是一个新概念，所以我发现除了“标准”内存斐波那契数列之外，我很难想到其他任何东西。

为了将数据类型 'a' 实例化为 Memoizable，我需要在其上定义一个函数 memoize (::(a-> v) -> a -> v)。

我在类(Eq、Ord、Show)中有一个数据类型数据公式。我将不得不定义自己的实例声明，但不知道期望的函数是什么。

这个函数究竟应该定义什么才能使内存起作用？包描述没有对此进行详细说明，我怀疑函数应用程序(符合类型签名)是否会加快速度。

Answer 1

您应该阅读有关类型类的内容。这是我对这个包的理解。

给出如下定义:

class Memoizable a where
  memoize ∷ (a → v) → a → v

你应该把 memoize 函数想象成这样:

memoize :: (Memoize a) => (a → v) → a → v

即:如果声明了 Memoize a 的实例，您可以将它应用于从 a 到 v 的函数。包声明一些基本类型的实例，如 Int

因此，如果你想内存compute::Int -> WidgetData，你应该使用具有相同类型的memoize compute而不做任何事情。

如果你想内存一个函数，该函数将一个没有内存实例的类型作为输入，你必须自己声明它。更有可能的是，您应该依靠像 deriveMemoizable 这样的模板函数来为您做这件事:

{-# LANGUAGE TemplateHaskell #-} -- put this at the top

deriveMemoizable ''T

I doubt function application (which fits the type signature) will speed anything up.

这取决于手头的问题。如果 compute 开销很大，并且您使用相同的输入调用它两次，它会存储结果并避免计算两次。如果不是这种情况，您将增加程序的内存使用量而没有任何好处。