Comptage du nombre d'éléments dans une liste qui satisfont le prédicat

Ne Haskell bibliothèque standard disposent d'une fonction qui étant donné une liste et d'un prédicat, renvoie le nombre d'éléments de satisfaction que prédicat? Quelque chose comme de type (a -> Bool) -> [a] -> Int. Mon hoogle recherche n'a pas renvoyé de quelque chose d'intéressant. Actuellement, je suis en utilisant length . filter pred, dont je ne trouve pas particulièrement élégant. Mon cas d'utilisation semble être assez commun d'avoir une meilleure solution en bibliothèque que ça. Est-ce le cas ou est-ce mon mauvais pressentiment?

InformationsquelleAutor missingfaktor | 2012-01-30

functional-programming haskell

41

La length . filter p mise en œuvre n'est pas aussi mauvais que vous le suggérez. En particulier, il n'a qu'constante de la surcharge de la mémoire et de la vitesse, donc oui.

Pour des choses que d'utiliser le volet de la fusion, comme le vector paquet, length . filter p sera réellement optimisés de façon à éviter de créer un vecteur intermédiaire. Listes, cependant, utiliser ce qu'on appelle foldr/build de la fusion à l'heure actuelle, qui n'est pas tout à fait assez intelligent pour optimiser length . filter p sans créer de façon linéaire à grande thunks que le risque de débordements de pile.

Pour plus de détails sur les flux de fusion, voir ce document. Si je comprends bien, la raison de ce flot de fusion n'est pas actuellement utilisé dans les principales Haskell bibliothèques, c'est que (comme décrit dans le papier) à environ 5% de programmes de façon spectaculaire pire lors de la mise en œuvre sur le dessus de la base de flux bibliothèques, tandis que les foldr/build optimisations peuvent jamais (à ma connaissance) de faire de la performance activement pire.
- +1, je ne savais pas à propos de cette optimisation. De grandes choses.
- C'est vraiment une des choses les plus cool sur Haskell: vous pouvez spécifier des règles de réécriture dans votre propre code qui sont utilisés par l'optimiseur, et de les utiliser pour obtenir terriblement modulable et efficace du code.
- D'accord. Haskell rochers!
- Mais le point est, vous ne devriez pas écrire votre propre code pour cela: vous devez simplement utiliser length . filter p, et la confiance dans l'optimiseur.
- J'ajouterais count pred = length . filter pred à mon utils.
- Qui fonctionne aussi...mais un conseil: vous obtiendrez de meilleurs résultats si vous utilisez un { -# INLINE count #- } pragma au-dessus de votre déclaration de count. (Où les "meilleurs résultats" se réfère à "l'optimiseur d'obtenir plus de possibilités de faire sa chose.")
- Merci! Je n'étais pas au courant pragma soit. Je vous suggère de l'ajouter à votre réponse aussi.
- La messagerie unifiée. Quelqu'un d'autre en plus de me confirmer que c'est vraiment bon? Je ne suis plus sûr que la longueur est construit avec foldr pour déclencher la fusion de ce genre.
- La Fusion se passe quand un "bon consommateur" consomme le résultat d'un "bon producteur". Les deux sont répertoriés ici, et length n'est pas inclus. Voir aussi: GHC #876: la longueur n'est pas un bon consommateur.
- La droite. Euh. Dois-je supprimer ma réponse, ou quoi? Je suis vraiment honte maintenant d'avoir beaucoup upvotes pour une mauvaise réponse...même si je suppose à partir de ce rapport de bug que la longueur était à certains point d'un bien de consommation?
- (@missingfaktor: vous aurez besoin de unaccept cette réponse avant que je puisse le supprimer. Bleahhhhh.)
- Je ne pense pas que vous devriez supprimer cette réponse. Juste frapper la inexactes bits. C'est la convention.
- Mis à jour avec un bon nombre de détails sur le pourquoi cela ne fonctionne pas, et quelques façons dont il fonctionne (c'est à dire la vector package).
InformationsquelleAutor Louis Wasserman
6

Non, il n'y a pas de fonction prédéfinie qui fait cela, mais je dirais que length . filter pred est, en fait, une élégante mise en œuvre; il est aussi proche que vous pouvez obtenir à l'expression de ce que tu veux dire sans l'invocation de la notion directement, ce qui vous ne pouvez pas faire si vous êtes à la définir.

La seule alternative serait une fonction récursive ou un pli, qui OMI serait moins élégante, mais si vous voulez vraiment:
```
foo :: (a -> Bool) -> [a] -> Int
foo p = foldl' (\n x -> if p x then n+1 else n) 0
```
C'est fondamentalement juste d'inlining length dans la définition. Comme pour les nommer, je dirais count (ou peut-être countBy, depuis count est raisonnable nom de la variable).
- +1, Il apparaît alors, je vais définir une nouvelle fonction dans mon utils. Merci pour la confirmation, et pour les conseils concernant le nom de la fonction.
- Je conseille à l'encontre de la définition d'une nouvelle fonction dans votre utils. length . filter pred sera plus lisible. Si vous trouvez vous-même le répéter plus et plus, il convient de la définir dans un cadre relativement étroit (par exemple, un where liaison ou un désexporter fonction de niveau supérieur). Mais si vous le mettez dans un module utils, des tiers lecture de votre code devra creuser jusqu'à comprendre ce que votre code est en train de faire.
InformationsquelleAutor ehird
5

Haskell est un langage de haut niveau. Plutôt que de proposer une fonction pour chaque combinaison de circonstances que vous pourriez jamais rencontrer, il vous fournit avec un petit ensemble de fonctions qui couvrent l'ensemble des notions de base, et vous collez ensuite ces ensemble comme nécessaire pour résoudre votre problème est actuellement à portée de main.

En termes de simplicité et de concision, c'est élégant, c'est tout. Donc oui, length . filter pred est absolument de la solution standard. Comme autre exemple, prenons elem, qui (comme vous le savez) vous indique si un élément est présent dans une liste. La norme de référence de mise en œuvre de ce qui est réellement
```
elem :: Eq x => x> [x] -> Bool 
elem x = foldr (||) Faux . carte (x ==) 
```
En d'autres termes, comparer chaque élément de la liste de l'élément cible, la création d'une nouvelle liste de Booléens. Ensuite, pliez la logique OU de la fonction au cours de cette nouvelle liste.

Si cela semble inefficace, essayez de ne pas s'en soucier. En particulier,
1. Le compilateur peut souvent optimiser l'écart temporaire des structures de données créé par ce type de code. (Rappelez-vous, c'est façon standard écrire du code dans Haskell, de sorte que le compilateur est à l'écoute de traiter avec elle.)
2. Même si il ne peut pas être optimisée, de loin, la paresse rend souvent l'exemple de code assez efficace quand même.
(Dans cet exemple précis, le OU la fonction terminer la boucle dès qu'un match est vu comme ce qui se passerait si vous codée à la main elle-même.)

En règle générale, écrire du code en collant ensemble des pré-fonctions existantes. Modifier ce que si la performance n'est pas assez bon.
- Merci pour votre réponse, +1. J'ai été en utilisant la programmation fonctionnelle pour assez longtemps, et je suis bien conscient des choses que vous avez dit dans votre réponse, mais quand j'ai un motif répétitif que celui qui est discuté ici, le facteur I dans une fonction séparée.
- Ici c'est une philosophie de la page de Facteur de langage de programmation, une langue où la composition est le façon de faire les choses, et la plupart du code est écrit dans le point-gratuitement. Avoir un coup d'oeil. Beaucoup de ces lignes directrices s'appliquent quelle que soit la langue, et il m'arrive de les suivre. Vous trouverez les mêmes conseils dans Leo Brodie est "la Pensée de Suite", qui est un grand livre sur le développement de logiciels en général.
- a smallish set of functions that cover all of the basics, and you then glue these together as required to solve whatever problem is currently at hand dans mon livre, c'est la définition même de faible niveau
InformationsquelleAutor MathematicalOrchid
0

C'est mon amateur solution à 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
```
InformationsquelleAutor JayJay

Vous devez vous connecter pour publier un commentaire.