¿Cómo evitar el cálculo innecesario?

Question

Necesito devolver falso si una prueba falla para más de 3 elementos en una lista. ¿Hay algo que pueda hacer para optimizar?

isItemOk :: Integer -> Boolean 
isItemOk = (some costly opernation) 

Esta es la función que estoy tratando de optimizar,

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ([ 1 | x <- [1.1000], isItemOk x ]) 

Mi intento de optimización, suponiendo que tomar si encuentra 4 elementos no buscará más.

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum (take 4 [ 1 | x <- [1.1000], isItemOk x ]) 

Thanks.

Answer 1

sólo puede utilizar filter con algo que comprueba si hay elementos que fallan, entonces take 4 y ver cuántos elementos que tiene con length.

La evaluación diferida significa que no se molestará en comprobar nada después de encontrar esos cuatro, por lo que habrá terminado. Por supuesto, si la prueba falla para tres o menos elementos, revisará toda la lista, pero no hay nada que puedas hacer al respecto.

Lo importante para evitar es algo así como "contar los elementos que no pasan la prueba", o "filtrar y luego obtener la duración del resultado", o algo por el estilo. Sin usar take o algo similar primero, hacerlo obligará a verificar toda la lista. Esta es una versión más general del consejo "use null o coincidencia de patrones para verificar listas vacías" que a menudo se brinda a los principiantes. ¡Pero parece que ya estás evitando ese error!

Answer 2

Para un número bajo como 3, puede usar la coincidencia de patrones.

case filter isItemOk xs of 
    x1 : x2 : x3 : _ -> ... 
    _    -> ... 

Answer 3

primer lugar quisiera reescribir su función un poco, ya

isListOk :: Bool 
isListOk = length (filter isItemOk [1 .. 1000]) <= 3 

es sin duda más idiomática de su versión. (Tenga en cuenta que también he cambiado la firma tipo que el suyo era incorrecto. Por otra parte, debería haber escrito 1 .. 1000 en lugar de 1.1000.)

La evaluación perezosa es su mejor amigo aquí, ya que por lo general asegurarse de que no hay cálculos innecesarios serán realizado.

Desafortunadamente, su uso de length (o el mapeo de cada elemento de una lista a 1 y luego sumar la lista resultante, como lo hace) se interpone en el camino aquí. Es decir, length es estricto en el lomo de la lista: solo puede producir la longitud de la lista si la evalúa hasta el final, lo que, en este caso, significa que su programa tendrá que ejecutar su cheque mil veces .

Una solución sería combinar el cálculo de la longitud (es decir, El recorrido de la columna vertebral de la lista) y la prueba si la longitud calculada no supera un determinado umbral en una sola función que es, de hecho, perezoso en la columna vertebral de la lista de parámetros:

isNotLongerThan :: [a] -> Integer -> Bool 
isNotLongerThan []  n = n >= 0 
isNotLongerThan (_ : xs) n = n >= 1 && isNotLongerThan xs (n - 1) 

y luego escribir

isListOk :: Bool 
isListOk = filter isItemOk [1 .. 1000] `isNotLongerThan` 3 

Para una solución reutilizable, puede, por supuesto, tanto abstracto sobre el predicado y el umbral:

forNoMoreThan :: (a -> Bool) -> Integer -> [a] -> Bool 
forNoMoreThan p n = (`isNotLongerThan` n) . filter p 

isListOk :: Bool 
isListOk = (isItemOk `forNoMoreThan` 3) [1 .. 1000] 

Por último, como señala Hammar, si su trillaste viejo es lo suficientemente pequeño y fijo, simplemente puede usar la coincidencia de patrones para determinar si una lista es lo suficientemente corta.

Answer 4

Me gustaría aprovechar esta oportunidad para exagerar lazy natural numbers un poco. El uso de esta biblioteca y genericLength, sólo podemos escribir

import Data.Number.Natural 
import Data.List 
isListOk = (3 :: Natural) >= genericLength (filter isItemOk [1..1000]) 

y va a hacer más trabajo de lo que tiene que: esta función se encuentra como máximo cuatro elementos bien antes de regresar. Por ejemplo:

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined)) 
False