haskell - 列表理解占用太多内存

Question

我是 Haskell 的初学者，用它解决了 Project Euler 的大约 50 个问题。但现在我被困在 problem 66 .问题是编译后的代码( ghc -O2 --make problem66.hs )在 10-20 秒后占用了我机器的所有可用内存。我的代码如下所示:

-- Project Euler, problem 66

diophantine x y d = x^2 - d*y^2 == 1

minimalsolution d = take 1 [(x, y, d) | y <- [2..],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

issquare x = (round $ sqrt $ fromIntegral x)^2 == x

main = do
    print (map minimalsolution (filter (not . issquare) [1..1000]))

我有一种预感，问题在于 minimalsolution 的列表推导式中的无限列表。 .

我实际上认为由于懒惰，Haskell 只会评估列表直到找到一个元素(因为 take 1 )，并在途中丢弃所有 diophantine 的所有元素。计算结果为 False .我错了吗？

有趣的是，我在 ghci 中没有看到这种行为。是因为 ghci 内部的处理速度太慢，我只能等到我看到内存消耗爆炸 - 还是其他原因？

请勿剧透。我想知道的是极端内存消耗来自哪里以及我如何解决它。

Answer 1

我之前没有介绍过，所以欢迎扔石头的人。

Haskell 确定 [2..] 是一个常量，并且会为列表的每个元素重用，尽管 take 1 只使用了该列表的一个元素；所以它记住列表以计算同一列表的 future 元素。您在计算 d=61 时陷入困境。

编辑:

有趣的是，这个终止于 [1..1000]:

minimalsolution d = take 1 [(x, y, d) | y <- [2..] :: [Int],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

刚刚添加 :: [Int] .内存使用看起来稳定在 1MB。使用 Int64 会重现该问题。

minimalsolution d = take 1 [(x, y, d) | y <- [2..] :: [Int64],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

编辑:

好吧，正如所建议的那样，差异是由溢出引起的。 d=61 的解被报告为 (5983,20568,61)，但 5983^2 远不及 61*20568^2。