在Haskell中记忆化？

Question

有关如何有效地解决Haskell中以下函数的所有问题的大量建议 (n > 108)

f(n) = max(n, f(n/2) + f(n/3) + f(n/4))

我已经在Haskell中看到了用于记忆斐波那契数的记忆示例，其中涉及（懒惰地）计算直到所需n的所有斐波那契数。但是在这种情况下，对于给定的n，我们只需要计算很少的中间结果。

谢谢

Answer 1

并非最有效的方法，但要记住：f = 0 : [ g n | n <- [1..] ]&nbsp; &nbsp; where g n = max n $ f!!(n `div` 2) + f!!(n `div` 3) + f!!(n `div` 4)请求时f !! 144，将检查是否f !! 143存在，但不计算其确切值。它仍然设置为某些未知的计算结果。唯一需要计算的精确值。因此，最初，就计算多少而言，该程序一无所知。f = ....&nbsp;当我们发出请求时f !! 12，它开始进行一些模式匹配：f = 0 : g 1 : g 2 : g 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...现在开始计算f !! 12 = g 12 = max 12 $ f!!6 + f!!4 + f!!3递归地对f提出了另一个要求，因此我们计算f !! 6 = g 6 = max 6 $ f !! 3 + f !! 2 + f !! 1f !! 3 = g 3 = max 3 $ f !! 1 + f !! 1 + f !! 0f !! 1 = g 1 = max 1 $ f !! 0 + f !! 0 + f !! 0f !! 0 = 0现在我们可以滴一些f !! 1 = g 1 = max 1 $ 0 + 0 + 0 = 1这意味着程序现在知道：f = 0 : 1 : g 2 : g 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...继续滴滴答答：f !! 3 = g 3 = max 3 $ 1 + 1 + 0 = 3这意味着程序现在知道：f = 0 : 1 : g 2 : 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...现在我们继续计算f!!6：f !! 6 = g 6 = max 6 $ 3 + f !! 2 + 1f !! 2 = g 2 = max 2 $ f !! 1 + f !! 0 + f !! 0 = max 2 $ 1 + 0 + 0 = 2f !! 6 = g 6 = max 6 $ 3 + 2 + 1 = 6这意味着程序现在知道：f = 0 : 1 : 2 : 3 : g 4 : g 5 : 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...现在我们继续计算f!!12：f !! 12 = g 12 = max 12 $ 6 + f!!4 + 3f !! 4 = g 4 = max 4 $ f !! 2 + f !! 1 + f !! 1 = max 4 $ 2 + 1 + 1 = 4f !! 12 = g 12 = max 12 $ 6 + 4 + 3 = 13这意味着程序现在知道：f = 0 : 1 : 2 : 3 : 4 : g 5 : 6 : g 7 : g 8 : g 9 : g 10 : g 11 : 13 : ...因此，计算是相当懒惰的。该程序知道for的某些值f !! 8等于g 8，但是不知道是什么g 8。