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

Question

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

我目前正在处理problem 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 个输入。因此，您需要 6 天的时间来计算最多 5e15 的解决方案。但当然，即使是算法的最佳优化也永远无法让您接近这个速度。正如欧拉计划问题的常见情况一样，您必须先进行一些更高级的数学运算来缩小问题的规模，然后才能使用计算机解决问题。