Haskell'计数发生'功能

Question

我count在Haskell中实现了一个函数,我想知道这会在大型列表上表现得很糟糕:

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

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

编辑:@Higemaru建议的重构

Answer 1

长度以线性时间运行到列表的大小,是的.

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

Answer 2

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

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

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