在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..] ]

    where g n = max n $ f!!(n `div` 2) + f!!(n `div` 3) + f!!(n `div` 4)

请求时f !! 144，将检查是否f !! 143存在，但不计算其确切值。它仍然设置为某些未知的计算结果。唯一需要计算的精确值。

因此，最初，就计算多少而言，该程序一无所知。

f = .... 

当我们发出请求时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 !! 1

f !! 3 = g 3 = max 3 $ f !! 1 + f !! 1 + f !! 0

f !! 1 = g 1 = max 1 $ f !! 0 + f !! 0 + f !! 0

f !! 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 + 1

f !! 2 = g 2 = max 2 $ f !! 1 + f !! 0 + f !! 0 = max 2 $ 1 + 0 + 0 = 2

f !! 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 + 3

f !! 4 = g 4 = max 4 $ f !! 2 + f !! 1 + f !! 1 = max 4 $ 2 + 1 + 1 = 4

f !! 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。