haskell 内存不足，列表有限

Question

我尝试运行中等输入时内存不足，例如：

variation_models 15 25

同样为 ncars 运行更高的数字似乎在速度和内存使用方面产生了巨大的差异。

放缓是预料之中的（有更多的东西可以比较），但内存使用量的指数增长对我来说没有意义

import Control.Monad

orderedq f [] = True
orderedq f (x:[]) = True
orderedq f (x:y:zs) = f x y && orderedq f (y:zs)

num_orderedq = orderedq (<=)

adds_up_to n xs = n == sum xs

both_conditions f g xs = f xs && g xs

variation_models ncars nlocations =
  filter (both_conditions (adds_up_to nlocations) num_orderedq) $ replicateM ncars [1..nlocations-ncars+1]

是什么导致了内存使用量的巨大差异？replicateM?

Answer 1

我认为您在其他地方已经看到，您的特定问题（创建总和为给定数字的有序整数列表）可以使用替代算法更好地解决，而不是过滤大量整数列表。

但是，回到您最初的问题，可以构造一个等效的：

replicateM p [1..n]

它以指数时间（当然）但恒定空间运行。

问题是这个表达式或多或少等价于递归：

badPower 0 _ = pure []
badPower p n = [x:xs | x <- [1..n], xs <- badPower (p-1) n]

因此，在列表推导中，对于每个选择的x，badPower (p-1) n需要从头开始重新生成整个列表。GHC 很明智地决定保留badPower (p-1) n，这样就不需要每次都重新计算。因此，badPower p n调用需要将整个badPower (p-1) n列表保存在内存中，这已经考虑了n^(p-1)元素和指数内存使用，甚至不考虑badPower (p-2) n等。

如果您只是翻转隐式循环的顺序：

goodPower 0 _ = pure []
goodPower p n = [x:xs | xs <- goodPower (p-1) n, x <- [1..n]]

这解决了问题。即使列表goodPower (p-1) n是“大”的，我们还是取它的第一个元素，n为每个值使用它几次x，然后可以丢弃它并移动到下一个元素。因此，goodPower (p-1) n可以在使用时进行垃圾收集。

请注意，goodPower以与 不同的顺序生成元素，badPower列表的第一个坐标变化最快，而不是最后一个。（如果这很重要，你可以map reverse $ goodPower ...。虽然reverse“慢”，它只适用于这里的短名单。）

无论如何，以下程序（实际上）永远运行，但在恒定空间中运行：

power :: Int -> [a] -> [[a]]
power 0 _ = [[]]
power p lst = [x:xs | xs <- power (p-1) lst, x <- lst ]

main = do
  print $ length (power 15 [1..11])