如何在Data.Function.Memoize中使用memoize函数

Question

在未能构建我自己的memoization表之后,我转向了所述类并尝试使用它来加速Fibonacci序列的双递归定义:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

我曾尝试过memoize几种方式使用该类的功能,但即使是下面的结构看起来也很慢(吃10秒fib 33):

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = memoize fib (n-1) + memoize fib (n-2)

fib' :: Int -> Int
fib' n = memoize fib n

我尝试过memoize以其他方式进行分发,但性能似乎没有提高.我知道有其他方法来解决这个问题,特别是计算得更有效,但对于我原来的问题,我想使用Memoize包.所以我的问题是,如何通过memoize此包中的功能提高性能？

Answer 1

显然,只有你恰好做一次,然后多次调用它,它才有用.而在你的方法中,你一遍又一遍地记住这个功能.那不是主意!

fib' n = memoize fib n

是一个正确的开始,但由于一个微妙的原因,它将无法正常工作:它不是一个恒定的应用形式,因为它明确提到它的论点.

fib' = memoize fib

是正确的.现在,为了实现这个fib功能,您必须参考记忆版本.

fib n = fib' (n-1) + fib' (n-2)

你会看到:严格遵守DRY并避免尽可能多的样板文件让你获得正确的版本!