haskell - 如何在使用 GHC 编译的 Haskell 函数中找到分配？

Question

我正在使用 GHC 7.4 编译以下函数:

nodups' :: [Int] -> Bool
nodups' = ok empty
  where ok _ [] = True
        ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns
        member n word = testBit word n
        insert n word = setBit word n
        empty = 0 :: Int

该函数在小整数列表中查找重复元素。套装 seen是将一组小整数表示为位向量。分析器(使用 ghc -prof -auto-all 运行)声称 ok功能占总体分配的 22%。使用 -ddump-simpl 查看输出，我不明白为什么这段代码正在分配。我查了一下，据我所知，它没有为对 insert 的调用分配一个 thunk。 .

我应该看什么来识别正在分配的代码部分？

Answer 1

一般来说

我知道函数式语言的简单(科学)实现，如果我没记错的话，有 G-Machine可以与 Haskell 一起使用。

这意味着(再次，如果我没记错的话)您的程序状态表示为“树”，其中节点(为了简单起见)是您在代码中使用的函数。叶子将是它的论据。然后，“G-Maschine”沿着“Spine”(节点的左侧链)查找并在可用的“Functions”(“Supercombinators”？)集合中查找它可以应用的模式匹配。如果一个 物质匹配从 中识别左侧然后将其替换为 右侧 的定义。

这意味着即使是简单的行

ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns

甚至

(n:ns) = ns

在计算机内存中做某事，即匹配模式

       ...
     ...
    (:)
   /   \
  n     ns

并将其替换为

       ...
     ...
    ns

最终结果可能会比输入消耗更少的内存，但这是一个动态步骤，因此必须在某个地方进行。如果一遍又一遍地重复(在“紧密循环”中)，那么这会让你的 CPU 很忙，你的内存也会很忙——只是因为 G-Machine 正在运行。 (正如我所说，我不确定 G-Machine 概念是否适用于此，但我想它是类似的)。

具体猜测

    member n word = testBit word n
    insert n word = setBit word n

除此之外，我还有一些怀疑。 testBit和 setBit看起来像列表上的索引操作。如果是的话，可能需要一些工作。如果它们是正确的数组，那就没问题了。如果它们是一种 map 或集合......嗯......可能涉及昂贵的散列？还是通过使用大量(昂贵？)比较操作的平衡树来实现？