Haskell primer prueba

Question

Soy nuevo en Haskell, y estoy tratando un poco:

isPrime :: Integer->Bool 
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0]) 

Tengo un par de preguntas.

1. ¿Por qué cuando intento cargar las .hs, WinHugs dicen: Los casos de (Floating Integer, RealFrac Integer) necesarios para la definición de isPrime?
2. Cuando el intérprete encuentra un elemento en el conjunto de la derecha, se detiene inmediatamente o computa todo el conjunto? Creo que sabes lo que quiero decir.

Disculpe mi inglés.

Answer 1

1) El problema es que sqrt tiene el tipo (Floating a) => a -> a, pero intenta utilizar un Entero como argumento. Por lo tanto, debe convertir su entero primero en flotante, p.escribiendo sqrt (fromIntegral x)

2) No veo ninguna razón por la cual == no deben ser perezoso, pero para la prueba de una colección vacía que puede utilizar la función null (que es, sin duda perezoso, ya que trabaja en las listas infinitas):

isPrime :: Integer->Bool 
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0] 

Pero para obtener una solución más idiomática, divida el problema en sub-problemas más pequeños. En primer lugar, necesitamos una lista de todos los elementos y con y * y < = x:

takeWhile (\y -> y*y <= x) [2..] 

entonces necesitamos sólo los elementos que dividen x:

filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..]) 

entonces tenemos que comprobar si esa lista está vacío:

isPrime x = null (filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..])) 

Y si esto se parece a lispy a usted, reemplazar algunos de los parens con $

isPrime x = null $ filter (\y -> x `mod` y == 0) $ takeWhile (\y -> y*y <= x) [2..] 

Para mayor claridad se puede "subcontratar" la lambdas:

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where 
    divisible y = x `mod`y == 0 
    notTooBig y = y*y <= x 

Se puede hacer casi "legible" mediante la sustitución del filtro $ nula con no $ ninguna:

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where 
    divisible y = x `mod`y == 0 
    notTooBig y = y*y <= x 

Answer 2

1. Debido sqrt tiene el tipo Floating a => a -> a. Esto significa que la entrada debe ser del tipo Floating y la salida será del mismo tipo. En otras palabras, x debe ser del tipo Floating. Sin embargo, ha declarado que x es del tipo Integer, que no es del tipo Floating. Además, floor necesita un tipo RealFrac, por lo que x también debe ser así.

   El mensaje de error indica que usted fija que al hacer Integer un tipo Floating (mediante la definición de una instancia Floating Integer (y lo mismo para RealFrac).

   Por supuesto, esto no es el enfoque correcto en este caso. Más bien se debe utilizar para convertir fromIntegralx a un Real (que es una instancia de Floating y RealFrac) y luego darle eso a sqrt.

2. Sí. tan pronto como == ve que el operando de la derecha tiene una Al menos un elemento, sabe que no es igual a [] y devuelve False.

   Una vez dicho esto, null es una forma más idiomática de comprobar si una lista está vacía que [] ==.

Answer 3

En cuanto al segundo punto, se detiene, por ejemplo:

[] == [x | x <- [1..]] 

devoluciones False

Answer 4

1. creo WinHugs necesita importar un módulo para Entero y etc ... Prueba Int
2. El intérprete no calculará nada hasta que llame, por ejemplo isPrime 32 luego calculará la expresión de forma perezosa.

PS ¡su implementación isPrime no es la mejor implementación!

Answer 5

solución de Landei es grande, sin embargo, si quieres una aplicación más efficient¹ tenemos (gracias a BMeph):

-- list of all primes 
primes :: [Integer] 
primes = sieve (2 : 3 : possible [1..]) where 
    sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0] 
    possible (x:xs) = 6*x-1 : 6*x+1 : possible xs 

isPrime :: Integer -> Bool 
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where 
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0)) 
    divisible y = n `mod` y == 0 
    inRangeOf y = y * y <= n 

La 'eficiencia' viene f rom el uso de primos constantes. Mejora la búsqueda de dos maneras:

1. El tiempo de ejecución Haskell podría almacenar en caché los resultados de las invocaciones de manera posteriores no se evalúan
2. Elimina un rango de números por la lógica nota que el valor sieve es simplemente una tabla recursiva, donde dice el encabezado de la lista es primordial y se la agrega. Para el resto de las listas, si no hay otro valor ya en la lista que compone el número, entonces también prime possible es una lista de todos los primos posibles, ya que todos los primos posibles están en el forma 6 * k-1 o 6 * k-1, excepto 2 y 3 se aplica la misma regla para shortCircuit demasiado para rescatar rápidamente fuera de cálculos

Nota al pie por DF
¹ Sigue siendo una forma terriblemente ineficiente de encontrar números primos. No use la división de prueba si necesita números primos mayores a algunos miles, use un tamiz en su lugar. Hay varias implementaciones far moreefficient en hackage.