haskell - Haskell'计数出现'功能

Question

我在 Haskell 中实现了一个count函数，我想知道这在大型列表中是否会表现不佳：

count   :: Eq a => a -> [a] -> Int
count x =  length . filter (==x)

我相信length函数在线性时间内运行，这是正确的吗？

编辑：@Higemaru 建议的重构

Answer 1

长度与列表大小成线性关系，是的。

通常，您会担心您的代码必须通过列表两次：第一次进行过滤，然后一次计算结果列表的长度。但是，我相信这不会发生在这里，因为过滤器对列表的结构并不严格。取而代之的是，length 函数强制过滤列表中的元素进行，一次执行实际计数。

Answer 2

我想你可以让它稍微短一点

count :: Eq a => a -> [a] -> Int
count x = length . filter (x==)

（如果可以的话，我会写一个（低调的）评论）

Answer 3

这真的取决于清单。对于我的计算机上一个正常的、懒惰评估的Ints 列表，我看到这个函数在大约 2 秒内运行 10^9 元素，0.2 秒 10^8 和 0.3 秒 10^7，所以它似乎以线性运行时间。您可以通过+RTS -s -RTS在从命令行运行时将标志传递给可执行文件来自行检查。

我还尝试使用更多内核运行它，但它似乎没有做任何事情，只是稍微增加了内存使用量。

惰性计算的一个额外好处是您只需遍历列表一次。 filter并被length编译器变成一个循环（打开优化），这样你就可以节省内存和效率。