过滤器foo的内存使用情况[2..n] !! 0

Question

假设我有以下功能

small_div :: Int -> Int
small_div n = filter (\x -> n `rem` x == 0) [2..n] !! 0

这个函数的内存使用情况是多少？等效的C代码将是恒定的内存使用量,我相信Haskell的懒惰评估意味着它不会创建[2..n]的更多元素而不是找到第一个除数所需的元素,但ghc足够聪明才能进行跳转像...这样的东西

int small_div(int n) {
    for (int x = 2; x <= n; x++) {
        if (n % x == 0) {
            return x;
        }
    }
}

Answer 1

GHC 7.10和7.8.4(我测试的版本)非常智能,可以跳转到优化的示例.

我从互联网上查找了两个素数,15485863和67867967.当我编译并运行main = print $ small_div 15485863带有+RTS -s标志时,我的总堆分配为51 Kb.当我用67867967运行时,我也获得了51 Kb的分配.这意味着没有为列表的生成和过滤分配单元.

这是非常有可能通过所谓的优化foldr/build融合(filter并enumFromTo为Int-s都参加这种融合).