haskell - 过滤器 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。当我使用 +RTS -s 标志编译并运行 main = print $ small_div 15485863 时，我的总数堆分配为 51 Kb。当我用 67867967 运行相同的程序时，我也得到了 51 Kb 的分配。这意味着没有为列表的生成和过滤分配单元格。

它很可能被所谓的foldr/build优化了融合(filter 和 enumFromTo for Int -s 都参与这种融合)。