Haskell:从具有一百万个值的列表构建 IntMap 时，我应该得到 "Stack space overflow"吗？

Question

我的问题是，在 Haskell 中使用任何 Map 实现时，在处理一百万个值时总是会出现“堆栈空间溢出”。

我想要做的是处理一对列表。每对包含两个整数(不是整数，我用它们失败了，所以我尝试了整数)。我想遍历列表中的每一对并使用第一个 Int 作为键。对于每个唯一的键，我想建立一个第二个元素的列表，其中每个第二个元素都成对具有相同的第一个元素。所以我最后想要的是从 Int 到 Int 列表的“映射”。这是一个例子。

给出这样的对列表:

[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]

我想以这样的“ map ”结束:

{1 : [42,79,10], 2 : [11], 3 : [18,99]}

(我在上面使用类似 Python 的符号来说明“ map ”。我知道它不是 Haskell。它只是为了说明目的。)

所以我尝试的第一件事是我自己手工构建的版本，我对 Int 对的列表进行排序，然后通过列表构建一个新的对列表，但这次第二个元素是一个列表。第一个元素是键，即每对的第一个元素的唯一 Int 值，第二个元素是每个原始对的第二个值的列表，这些值将键作为第一个元素。

所以给出这样的对列表:

[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]

我最终得到一个像这样的对列表:

[(1, [42,79,10], (2, [11]), (3, [18,99])]

这很容易做到。但是有一个问题。 “排序”功能在原始列表(1000 万对)上的表现非常糟糕。我可以在不到一秒的时间内生成原始对列表。我可以在不到一秒钟的时间内将排序后的列表处理到我手工制作的 map 中。但是，对原始对列表进行排序需要 40 秒。

所以我考虑使用 Haskell 中内置的“Map”数据结构之一来完成这项工作。我的想法是构建我的原始对列表，然后使用标准 Map 函数构建标准 Map。

这就是一切都变成梨形的地方。它在 100,000 个值的列表上运行良好，但是当我移动到 100 万个值时，出现“堆栈空间溢出”错误。

所以这里有一些遇到问题的示例代码。请注意，这不是我想要实现的实际代码。它只是一个非常简化的代码版本，存在同样的问题。我真的不想将一百万个连续的数字分成奇数和偶数分区!!

import Data.IntMap.Strict(IntMap, empty, findWithDefault, insert, size)

power = 6

ns :: [Int]
ns = [1..10^power-1]

mod2 n = if odd n then 1 else 0

mod2Pairs = zip (map mod2 ns) ns

-- Takes a list of pairs and returns a Map where the key is the unique Int values
-- of the first element of each pair and the value is a list of the second values
-- of each pair which have the key as the first element.
-- e.g. makeMap [(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)] = 
--      1 -> [42,79,10], 2 -> [11], 3 -> [18,99]
makeMap :: [(Int,a)] -> IntMap [a]
makeMap pairs = makeMap' empty pairs
  where
    makeMap' m [] = m
    makeMap' m ((a, b):cs) = makeMap' m' cs
      where
        bs = findWithDefault [] a m
        m' = insert a (b:bs) m

mod2Map = makeMap mod2Pairs

main = do
  print $ "Yowzah"
  print $ "length mod2Pairs="++ (show $ length mod2Pairs)
  print $ "size mod2Map=" ++ (show $ size mod2Map)

当我运行这个时，我得到:

"Yowzah"
"length mod2Pairs=999999"
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

从上面的输出可以清楚地看出，当我尝试执行“makeMap mod2Pairs”时会发生堆栈空间溢出。

但在我天真的眼睛看来，这一切似乎都是通过一个对的列表，并为每对查找一个键(每对的第一个元素)和 A)，如果没有找到匹配项，则返回一个空列表或 B)如果确实找到匹配项，则返回先前插入的列表。在任何一种情况下，它都是“找到”列表中的第二个元素，并使用相同的键将其插入回 Map 中。

(PS 而不是 findWithDefault，我也尝试过查找并处理 Just and Nothing 用例，但无济于事。)

我已经查看了有关各种 Map 实现的 Haskell 文档，并从 CPU 和内存(尤其是堆栈内存)方面的性能角度来看，似乎 A) 严格实现和 B) 一个关键的实现是整数将是最好的。我也尝试过 Data.Map 和 Data.Strict.Map，它们也遇到了同样的问题。

我确信问题出在“ map ”实现上。我对吗？为什么会出现堆栈溢出错误，即 Map 实现在后台执行了什么导致堆栈溢出？它是否在幕后进行了大量递归调用？

任何人都可以帮助解释发生了什么以及如何解决这个问题？

Answer 1

我没有足够旧的 GHC 来检查(这对我来说很好用，而且我没有 7.6.3 像你那样)，但我猜你的 makeMap'太懒了。可能这会解决它:

makeMap' m ((a, b):cs) = m `seq` makeMap' m' cs

没有它，您将构建一个百万级深度的嵌套 thunk，而深度嵌套的 thunk 是导致 Haskell 中堆栈溢出的传统方式。

或者，我会尝试更换整个 makeMap使用 fromListWith 实现:

makeMap pairs = fromListWith (++) [(k, [v]) | (k, v) <- pairs]