如何存储和引用递归函数的中间值

Question

最近几周我刚刚开始学习 Haskell。我正在使用 Project Euler 问题来学习，目前正在尝试弄清楚是否有可能。不找人给我答案，只需要帮助理解 Haskell 中的数据结构。

我目前正在处理问题 484，它指定了一个递归函数。编写函数不是问题，我目前有：

import Math.NumberTheory.Primes
import Data.Maybe
import Data.List

derivative :: Integer -> Integer
derivative x
    | x < 2 = error "Error: Attempt to evaluate outside domain"
    | isPrime x = 1
    | otherwise = (derivative a)*b + a*(derivative b)
    where
        [a, b] = int_split x

--this function find the first pair of divisors
int_split :: Integer -> [Integer]
int_split n = [first_div, n `div` first_div] where
              first_div = fromJust $ find (\x -> (n `mod` x) ==0) [2..]

这似乎工作正常，因为计算与问题给出的样本值相匹配。问题是我需要为非常大的值计算这个，通过 5x10^15 获取所有值。将所有值提高到 ~10^8 运行得非常快，但超过它变得非常慢。简单地使用 map 绝对是低效的，因为它没有利用我们可以引用先前计算的值这一事实。

我的想法是更改我的函数以将值存储在查找表中，因为它们被计算为函数能够引用。我尝试使用 Data.Map 来存储值，但我无法弄清楚如何以递归方式将其集成到我的函数中。这在 Haskell 中可能吗？或者有没有我没有想到的更好的方法来存储和使用中间计算？

Answer 1

我真的不认为优化您当前的方法可以在合理的时间内为您提供您正在寻找的答案。假设您优化得如此之好，以至于您可以在单个时钟周期内计算出任何数字的解，并让我们为您提供一个相对正常的 3GHz 处理器。

$ units
You have: 3 giga hertz
You want: / day
        * 2.592e+14
        / 3.8580247e-15

即使速度如此之快，您每天也只能解决 2.5e14 个输入。因此，计算最多 5e15 的解需要 6 天时间。但当然，即使对算法进行了最佳优化，也永远无法让您接近那个速度。与欧拉项目问题的常见情况一样，在使用计算机解决问题之前，您必须先进行一些更高级的数学运算以缩小问题的规模。