haskell 计算列表中满足给定 predicate 的元素数

fnvucqvd  于 2023-01-09  发布在  其他
关注(0)|答案(6)|浏览(198)

Haskell标准库是否有一个函数,在给定一个列表和一个 predicate 的情况下,返回满足该 predicate 的元素数?类似于(a -> Bool) -> [a] -> Int类型。我的hoogle搜索没有返回任何有趣的结果。目前我使用的是length . filter pred,我并不认为这是一个特别优雅的解决方案,我的用例似乎足够常见,可以有一个更好的库解决方案。是这样吗?还是我的预感错了?

bksxznpy

bksxznpy1#

length . filter p的实现并不像你说的那么糟糕,特别是,它在内存和速度上只有恒定的开销,所以是的。
对于像vector包这样使用流融合的东西,length . filter p实际上会被优化以避免创建中间向量。然而,列表目前使用的是所谓的foldr/build融合,它还不够聪明,无法在不创建线性大thunk的情况下优化length . filter p,而thunk有堆栈溢出的风险。
有关流融合的详细信息,请参阅this paper。据我所知,目前主流Haskell库中没有使用流融合的原因是(如本文所述)当在基于流的库上实现时,大约5%的程序的性能会显著 * 变差 *,而foldr/build优化永远不会(AFAIK)使性能显著变差。

q1qsirdb

q1qsirdb2#

不,没有预定义的函数可以实现这一点,但我认为length . filter pred实际上是一个优雅的实现;这是你所能表达的最接近的东西,而不是直接调用这个概念,如果你定义它,你就不能直接调用它。
唯一的替代方法是递归函数或fold,这可能不太优雅,但如果您真的想这样做:

foo :: (a -> Bool) -> [a] -> Int
foo p = foldl' (\n x -> if p x then n+1 else n) 0

这基本上只是将length内联到定义中,至于命名,我建议使用count(或者countBy,因为count是一个合理的变量名)。

but5z9lq

but5z9lq3#

Haskell是一种高级语言,它不是为你可能遇到的每一种可能的情况组合提供一个函数,而是为你提供一个覆盖所有基础的小函数集,然后你根据需要将这些函数粘合在一起,以解决当前手头的任何问题。
就简单性和简洁性而言,这是最优雅的了。所以,length . filter pred绝对是标准解决方案。作为另一个例子,考虑elem,它(正如您可能知道的)告诉您给定的项是否存在于列表中。它的标准参考实现实际上是

elem :: Eq x => x -> [x] -> Bool
elem x = foldr (||) False . map (x ==)

换句话说,将列表中的每个元素与目标元素进行比较,创建一个新的布尔值列表,然后在这个新列表上叠加逻辑或函数。
如果这看起来效率很低,不要担心,特别是,
1.编译器经常会优化掉这样的代码所创建的临时数据结构(记住,这是用Haskell编写代码的标准方式,所以编译器会进行调整来处理它)。
1.即使它不能被优化掉,懒惰通常也会使这样的代码相当高效。
(In在这个特定的示例中,OR函数将在发现匹配项时立即终止循环-就像您自己手工编写代码时所发生的情况一样。)
一般来说,编写代码时要把已经存在的函数粘在一起,只有在性能不够好的时候才改变这种做法。

7vhp5slm

7vhp5slm4#

这是我对一个类似问题的业余解答。计算列表l中负整数的个数

nOfNeg l = length(filter (<0) l)
main = print(nOfNeg [0,-1,-2,1,2,3,4] ) --2
jucafojl

jucafojl5#

不,没有!
截至2020年,Haskell标准库中确实还没有这样的习语!然而,人们可以(也应该)插入一个习语howMany(类似于好的老any

howMany p xs = sum [ 1 | x <- xs, p x ]
-- howMany=(length.).filter

main = print $ howMany (/=0) [0..9]

尝试howMany=(长度.).过滤器

ctehm74n

ctehm74n6#

我会手动操作

howmany :: (a -> Bool) -> [a] -> Int 
howmany _ [ ] = 0
howmany pred (x:xs)  = if pred x then 1 + howmany pred xs 
                       else               howmany pred xs

相关问题