如何在使用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,我无法理解为什么这个代码正在分配.我检查过,据我所知,它没有为呼叫分配一个thunk insert.

我应该注意什么来识别我的代码分配部分？

Answer 1

一般来说

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

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

这意味着即使是简单的一行

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

甚至

(n:ns) = ns

正在计算机内存中执行某些操作，即匹配模式

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

并将其替换为

       ...
     ...
    ns

最终结果可能比输入消耗更少的内存，但这是一个动态步骤，因此必须在某个地方发生。如果这一过程一遍又一遍地重复（在“紧密循环”中），那么这将使您的 CPU 繁忙，也会使您的内存繁忙 - 只是因为 G 机正在运行。（正如我所说，我不确定 G 机概念是否适用于此，但我猜它是类似的东西）。

具体猜测

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

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