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

Question

我正在研究NP搜索问题,并被告知我可以通过使用所述包加快搜索过程.由于回忆对我来说是一个新概念,我发现除了"标准"记忆的斐波那契序列之外,我很难将其包围起来.

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

我有一个数据类型数据公式在类(Eq,Ord,Show)中.我将不得不定义自己的实例声明,但不知道预期的功能.

这个函数究竟应该为memoisation定义什么？包描述没有详细说明,我怀疑功能应用程序(适合类型签名)将加速任何事情.

Answer 1

你应该读一下类型类.以下是我对包装的理解.

给出以下定义:

class Memoizable a where
  memoize ? (a ? v) ? a ? v

您应该将memoize函数视为:

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

即:如果Memoize a声明了一个实例,你可以将它应用于一个函数.包声明了一些基本类型的实例Int

因此,如果你想要记忆compute :: Int -> WidgetData,你应该使用memoize compute具有相同类型而不做任何事情.

如果你想记住一个没有Memoize实例的输入类型的函数,你必须自己声明它.更有可能的是,您应该依赖模板函数deriveMemoizable来为您执行此操作:

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

deriveMemoizable ''T

我怀疑功能应用程序(适合类型签名)会加速任何事情.

这取决于手上的问题.如果compute价格昂贵,并且使用相同的输入调用它两次,它将存储结果并避免计算两次.如果不是这种情况,您将增加程序的内存使用量而不会有任何收益.