Compte le nombre d'éléments d'une liste qui satisfont le prédicat donné

Question

La bibliothèque standard de Haskell possède-t-elle une fonction qui, étant donné une liste et un prédicat, renvoie le nombre d'éléments satisfaisant ce prédicat ? Quelque chose comme avec le type (a -> Bool) -> [a] -> Int . Ma recherche sur Google n'a rien donné d'intéressant. J'utilise actuellement length . filter pred ce qui ne me semble pas être une solution particulièrement élégante. Mon cas d'utilisation semble être suffisamment courant pour qu'il y ait une meilleure solution de bibliothèque que celle-là. Est-ce le cas ou mon pressentiment est-il erroné ?

Answer 1

En length . filter p La mise en œuvre n'est pas aussi mauvaise que vous le laissez entendre. En particulier, elle n'a qu'une surcharge constante en mémoire et en vitesse, donc oui.

Pour les choses qui utilisent la fusion de flux, comme le vector l'emballage, length . filter p sera en fait optimisé afin d'éviter la création d'un vecteur intermédiaire. Les listes, cependant, utilisent ce qui est appelé foldr/build fusion pour l'instant, qui n'est pas assez intelligente pour optimiser l'utilisation de la technologie de l'information. length . filter p sans créer des morceaux de taille linéaire qui risquent de faire déborder la pile.

Pour plus d'informations sur la fusion des flux, voir ce document . Si je comprends bien, la raison pour laquelle la fusion des flux n'est pas utilisée actuellement dans les principales bibliothèques Haskell est que (comme le décrit l'article) environ 5 % des programmes sont très performants. pire lorsqu'il est mis en œuvre au-dessus de bibliothèques basées sur les flux, tandis que les foldr/build Les optimisations ne peuvent jamais (AFAIK) aggraver les performances.

Answer 2

Non, il n'y a pas de fonction prédéfinie qui fasse cela, mais je dirais que length . filter pred est en fait une implémentation élégante ; elle est aussi proche que possible de l'expression de ce que vous voulez dire sans invoquer directement le concept, ce que vous ne pouvez pas faire si vous le définissez.

Les seules alternatives seraient une fonction récursive ou un pli, qui seraient moins élégants, mais si vous y tenez vraiment :

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

Il s'agit en fait d'une simple mise en ligne length dans la définition. En ce qui concerne la dénomination, je suggérerais count (ou peut-être countBy puisque count est un nom de variable raisonnable).

Answer 3

Haskell est un langage de haut niveau. Plutôt que de fournir une fonction pour chaque combinaison possible de circonstances que vous pourriez rencontrer, il vous fournit un petit ensemble de fonctions qui couvrent toutes les bases, et vous pouvez ensuite les coller ensemble comme il se doit pour résoudre le problème qui se présente à vous.

En termes de simplicité et de concision, il n'y a rien de plus élégant. Donc, oui, length . filter pred es absolument la solution standard. Prenons un autre exemple elem qui (comme vous le savez peut-être) vous indique si un élément donné est présent dans une liste. L'implémentation de référence standard pour cela est en fait

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

En d'autres termes, comparez chaque élément de la liste à l'élément cible, en créant une nouvelle liste de Bools. Replier ensuite la fonction OU logique sur cette nouvelle liste.

Si cela vous semble inefficace, essayez de ne pas vous en préoccuper. En particulier,

1. Le compilateur peut souvent optimiser les structures de données temporaires créées par ce type de code. (N'oubliez pas qu'il s'agit de la méthode standard d'écrire du code en Haskell, de sorte que le compilateur est conçu pour le gérer).

2. Même s'il n'est pas possible de l'optimiser, la paresse rend souvent ce type de code assez efficace.

(Dans cet exemple précis, la fonction OR met fin à la boucle dès qu'une correspondance est trouvée - exactement comme si vous l'aviez codée vous-même).

En règle générale, il convient d'écrire le code en collant des fonctions préexistantes. Ne changez cela que si les performances ne sont pas suffisantes.

Answer 4

Voici ma solution amateur à un problème similaire. Compter le nombre d'entiers négatifs dans une liste l

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

Answer 5

Non, il n'y en a pas !

En 2020, il n'y a en effet pas encore d'idiome de ce type dans la bibliothèque standard de Haskell ! On pourrait (et devrait) cependant insérer un idiome howMany (ressemblant à la bonne vieille any )

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

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

Essayez howMany=(length.).filter