Data.MemoCombinators，我可以在哪里找到示例？ [英] Data.MemoCombinators, where can I find examples?

问题描述

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

http://hackage.haskell.org/packages/archive/data-memocombinators/ 0.3 / doc / html / Data-MemoCombinators.html＃t：备忘录

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

解决方案：

正如Hammar所描述的，不是将函数定义为：

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

使用memo2：

 输入限定的Data.MemoCombinators作为备注
 
 foo = Memo.memo2（Memo.list Memo.integral）Memo.integral foo'
其中...（用递归调用foo来定义foo'）
  

解决方案

库定义类型为 Memo a ，它是一个函数的memoizer，它使用类型的参数。理解如何使用这个库的关键是了解如何使用和组合这些记忆。

在简单的情况下，你有一个参数函数和一个简单的记忆器例如Fibonacci函数和用于 Integral 参数的记忆器。在这种情况下，我们通过将memoizer应用于要记忆的函数来获得memoized函数：

  fib = Memo.integral fib'
 where 
 fib'0 = 0 
 fib'1 = 1 
 fib'x = fib（x-1）+ fib（x-2）
  

有些记忆器会自定义它们的行为，例如 arrayRange 。在下面的例子中，如果 n 介于1和100之间，那么 fib n 只会被记忆。

  fib = Memo.arrayRange（1,100）fib'
其中... 
  

该库还提供了用于构建更简单的更复杂的记忆器的组合器。例如， list ，它将 a 的记事器转换为 [a] 。

最后，为了记忆多个参数的函数，有函数 memo2 和 memo3 ，它为每个参数添加一个记忆器并加上一个函数并返回一个记忆函数。

所以要记忆你的双参数函数，我们将需要使用 memo2 。我们可以为 Int 参数使用积分 memoizer，对于 [Int] 参数，我们可以使用 list integral 。把它们放在一起，我们可以得到这样的结果：

  memo2（列表积分）积分foo 
  
 
 
  memo2（ list $ arrayRange（1，10））（arrayRange（15，20））foo 
  
是否感觉，取决于你的应用程序。
 
This package has some functions to turn recursive functions into dynamic programming recursive functions, for better performance:

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

Unfortunately, they only have an example for the simplest type of function, and there are no examples on how to use a function of 2 variables. Where can I find an example of how to, for example, turn [Int] -> Int -> Int function into a dynamic-programming function? The documentation says memo2 takes two Memos as first arguments, but I'm not sure what that means.

Solution:

As Hammar described, instead of defining a function as:
foo :: [Int] -> Int -> Int
foo list value = ...
to use 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.)

解决方案
The library defines the type Memo a, which is a "memoizer" for functions taking arguments of type a. The key to understanding how to use this library is to understand how to use and compose these memoizers.

In the simple case, you have a single argument function and a simple memoizer, for example a Fibonacci function and a memoizer for Integral arguments. In such a case, we obtain the memoized function by applying the memoizer to the function to be memoized:
 fib = Memo.integral fib'
   where
     fib' 0 = 0
     fib' 1 = 1
     fib' x = fib (x-1) + fib (x-2)
Some memoizers take arguments to customize their behavior, for example arrayRange. In the following example, fib n will only be memoized if n is between 1 and 100.
fib = Memo.arrayRange (1, 100) fib'
  where ...
The library also provides combinators for building more complex memoizers out of simple ones. For example, list, which turns a memoizer for a into a memoizer for [a].

Finally, to memoize functions of multiple arguments there are the functions memo2 and memo3, which take a memoizer for each argument plus a function and returns a memoized function.

So to memoize your two-argument function, we will need to use memo2. We can use the integral memoizer for the Int argument, and for the [Int] argument we can use list integral. Putting this together, we get something like this:
memo2 (list integral) integral foo
However, you can also use more specific memoizers if you know the numbers are in some specified range. For example, if the numbers in the list are between 1 and 10 and the second argument is between 15 and 20:
memo2 (list $ arrayRange (1, 10)) (arrayRange (15, 20)) foo
Whether this makes sense or not, depends on your application.

                        
这篇关于Data.MemoCombinators，我可以在哪里找到示例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！