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])