promedio - multiplicar haskell

Contando el número de elementos en una lista que satisfacen el predicado dado

Question

¿La biblioteca estándar de Haskell tiene una función que da una lista y un predicado, devuelve la cantidad de elementos que satisfacen ese predicado? Algo así como con tipo (a -> Bool) -> [a] -> Int . Mi búsqueda de hoogle no me devolvió nada interesante. Actualmente estoy usando length . filter pred length . filter pred , que no creo que sea una solución particularmente elegante. Mi caso de uso parece ser lo suficientemente común como para tener una mejor solución de biblioteca que eso. ¿Es ese el caso o es mi premonición incorrecta?

Answer 1

Esta es mi solución aficionada a un problema similar. Cuenta el número de enteros negativos en una lista l

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

Answer 2

Haskell es un lenguaje de alto nivel. En lugar de proporcionar una función para cada combinación posible de circunstancias que pueda encontrar, le proporciona un conjunto pequeño de funciones que cubren todos los aspectos básicos, y luego las combina según sea necesario para resolver cualquier problema que esté a la mano.

En términos de simplicidad y concisión, esto es tan elegante como se pone. Entonces sí, length . filter pred length . filter pred es absolutamente la solución estándar. Como otro ejemplo, considere elem , que (como usted sabrá) le dice si un artículo dado está presente en una lista. La implementación de referencia estándar para esto es en realidad

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

En palabras de orden, compare cada elemento en la lista con el elemento objetivo, creando una nueva lista de Bools. A continuación, doble la función OR lógica sobre esta nueva lista.

Si esto parece ineficiente, trate de no preocuparse por eso. En particular,

1. El compilador a menudo puede optimizar estructuras temporales de datos creadas por código como este. (Recuerde, esta es la forma estándar de escribir código en Haskell, por lo que el compilador está sintonizado para manejarlo).

2. Incluso si no puede optimizarse, la pereza a menudo hace que dicho código sea bastante eficiente de todos modos.

(En este ejemplo específico, la función OR terminará el ciclo tan pronto como se vea una coincidencia, al igual que lo que sucedería si usted mismo lo codificara a mano).

Como regla general, escriba el código pegando las funciones preexistentes. Cambie esto solo si el rendimiento no es lo suficientemente bueno.

Answer 3

La length . filter p length . filter p implementación del length . filter p no es tan mala como sugiere. En particular, solo tiene una sobrecarga constante en memoria y velocidad, así que sí.

Para las cosas que usan fusión de secuencias, como el paquete de vector , length . filter p length . filter p realidad se optimizará para evitar la creación de un vector intermedio. Las listas, sin embargo, usan lo que se llama fusión foldr/build en este momento, que no es lo suficientemente inteligente como para optimizar la length . filter p length . filter p sin crear grandes cantidades lineales que arriesguen los desbordamientos de la pila.

Para obtener más información sobre la fusión de secuencias, consulte este documento . Según entiendo, la razón por la que la fusión de secuencias no se usa actualmente en las bibliotecas principales de Haskell es que (como se describe en el documento) aproximadamente el 5% de los programas empeora dramáticamente cuando se implementa en las bibliotecas basadas en secuencias, mientras que foldr/build las optimizaciones nunca pueden (AFAIK) empeorar el rendimiento.

Answer 4

No, no hay una función predefinida que haga esto, pero yo diría que es de length . filter pred length . filter pred es, de hecho, una implementación elegante; es lo más cercano que puede llegar a expresar lo que quiere decir sin simplemente invocar el concepto directamente, lo que no puede hacer si lo está definiendo.

Las únicas alternativas serían una función recursiva o un doblez, que IMO sería menos elegante, pero si realmente quieres:

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

Básicamente, esto es solo una length en la definición. En cuanto a la denominación, sugeriría count (o tal vez countBy , ya que count es un nombre de variable razonable).