Data.MemoCombinators,我在哪里可以找到示例？

Question

这个包有一些函数可以将递归函数转换为动态编程递归函数,以获得更好的性能:

http://hackage.haskell.org/packages/archive/data-memocombinators/0.3/doc/html/Data-MemoCombinators.html#t:Memo

不幸的是,它们只有最简单类型函数的示例,并且没有关于如何使用2个变量函数的示例.我在哪里可以找到如何将[Int] -> Int -> Int功能转换为动态编程功能的示例？文档说memo2需要两个Memos作为第一个参数,但我不确定这意味着什么.

解:

正如Hammar所描述的那样,而不是将函数定义为:

foo :: [Int] -> Int -> Int
foo list value = ...

使用memo2:

import qualified Data.MemoCombinators as Memo

foo = Memo.memo2 (Memo.list Memo.integral) Memo.integral foo'
  where ... (define foo' with recursive calls to foo.)

Answer 1

该库定义了类型Memo a,它是带有类型参数的函数的"memoizer" a.理解如何使用此库的关键是了解如何使用和组合这些存储器.

在简单的情况下,您有一个参数函数和一个简单的memoizer,例如Fibonacci函数和Integral参数的memoizer .在这种情况下,我们通过将memoizer应用于要记忆的函数来获取memoized函数:

 fib = Memo.integral fib'
   where
     fib' 0 = 0
     fib' 1 = 1
     fib' x = fib (x-1) + fib (x-2)

例如,一些记忆者会采用参数来定制他们的行为arrayRange.在以下示例中,fib n只有在n介于1和100之间时才会被记忆.

fib = Memo.arrayRange (1, 100) fib'
  where ...

该库还提供组合器,用于构建更简单的备忘录.例如,list将备忘录a转换为备忘录[a].

最后,为了记住多个参数的函数memo2,有函数和函数memo3,它们为每个参数加上一个函数并返回一个memoized函数.

所以要记住你的双参数函数,我们需要使用memo2.我们可以使用integralmemoizer作为Int参数,[Int]也可以使用我们可以使用的参数list integral.把它们放在一起,我们得到这样的东西:

memo2 (list integral) integral foo

但是,如果您知道数字在某个指定范围内,您还可以使用更具体的备忘录.例如,如果列表中的数字介于1和10之间,而第二个参数介于15和20之间:

memo2 (list $ arrayRange (1, 10)) (arrayRange (15, 20)) foo

这是否有意义取决于您的应用.