列表理解占用了太多的内存

Question

我是Haskell的初学者，用它解决了大约50个Euler项目问题，但现在我被困在问题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

无论它的价值是什么，我已经测试了这个六年后，这个问题不再出现。GHC 8.6.5的内存消耗仍然很低。我认为这确实是编译器中的一个问题，编译器在某个时候已经修复了。

Answer 2

我以前没写过，所以我们欢迎扔石头的人。

哈斯克尔决定..。是一个常量，对列表中的每个元素都重复使用，尽管只使用该列表中的一个元素；因此它会回溯列表，以计算相同列表的未来元素。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。

Answer 3

在理解过程中，在y的每个值上创建不必要的双实例。

我找不到一个解决方案，使用的列表理解没有空间爆破。但是使用递归重写会产生一个稳定的内存配置文件。

diophantine :: Int -> Int -> Int -> Bool
diophantine x y d = x^2 - d*y^2 == 1

minimalsolution ::  Int -> (Int, Int, Int)
minimalsolution d = go 2
  where
    d0 = fromIntegral d
    go a =
      let y = fromIntegral a
          x = round $ sqrt $ (d0*y^2+1) in
      if diophantine x y d then
        (x, y, d)
      else
        go (y+1)