计算列表中满足给定谓词的元素数量 [英] Counting number of elements in a list that satisfy the given predicate

问题描述

Haskell标准库有一个给定一个列表和一个谓词的函数，返回满足该谓词的元素的数量？类似于（a - > Bool） - > [a] - > INT 。我的hoogle搜索没有返回任何有趣的内容。目前我正在使用长度。过滤pred ，我不认为这是一个非常优雅的解决方案。我的使用案例似乎已经足够普遍，可以有更好的图书馆解决方案。是这种情况还是我的预感错了？

长度。过滤器p 的实现并不像你所说的那么糟糕。特别是，它在内存和速度上只有不断的开销，所以是的。

对于使用流融合的东西，比如 vector 包，长度。过滤器p 将实际进行优化，以避免创建中间向量。然而，列表目前使用所谓的 foldr / build 融合，这并不足够智能以优化长度。过滤p 而不创建可能会导致堆栈溢出的线性大thunk。

有关流融合的详细信息，请参阅本文。据我了解，目前Haskell主要库中没有使用流融合的原因是（如本文中所述），当在流的顶部实现时，大约5％的程序性能显着恶化基于库的库，而 foldr / build 优化永远无法（AFAIK）使性能变得更糟。

Does Haskell standard library have a function that given a list and a predicate, returns the number of elements satisfying that predicate? Something like with type (a -> Bool) -> [a] -> Int. My hoogle search didn't return anything interesting. Currently I am using length . filter pred, which I don't find to be a particularly elegant solution. My use case seems to be common enough to have a better library solution that that. Is that the case or is my premonition wrong?

解决方案

The length . filter p implementation isn't nearly as bad as you suggest. In particular, it has only constant overhead in memory and speed, so yeah.

For things that use stream fusion, like the vector package, length . filter p will actually be optimized so as to avoid creating an intermediate vector. Lists, however, use what's called foldr/build fusion at the moment, which is not quite smart enough to optimize length . filter p without creating linearly large thunks that risk stack overflows.

For details on stream fusion, see this paper. As I understand it, the reason that stream fusion is not currently used in the main Haskell libraries is that (as described in the paper) about 5% of programs perform dramatically worse when implemented on top of stream-based libraries, while foldr/build optimizations can never (AFAIK) make performance actively worse.

这篇关于计算列表中满足给定谓词的元素数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！