Haskell prime Test

Question

Ich bin neu in Haskell, und ich versuche, ein wenig:

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

Ich habe ein paar Fragen.

1. Warum, wenn ich versuche, die .hs zu laden, WinHugs sagen: Instanzen (Floating Integer, RealFrac Integer) zur Definition erforderlich von isPrime?
2. Wenn der Interpreter ein Element in der richtigen Menge findet, stoppt es sofort oder berechnet alle Mengen? Ich denke, du weißt, was ich meine.

Sorry über mein Englisch.

Answer 1

1) Das Problem ist, dass sqrt den Typ (Floating a) => a -> a hat, aber Sie versuchen, eine Ganzzahl als Argument zu verwenden. Sie müssen also Ihre Integer zuerst in eine Floating-Datei konvertieren, z.von sqrt (fromIntegral x)

2 schreiben) sehe ich keinen Grund, warum == sollte nicht faul sein, aber für den Test für eine leere Sammlung können Sie die null Funktion verwenden (was definitiv faul ist, wie es auf unendlichen Listen funktioniert):

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

Um jedoch eine idiomatische Lösung zu erhalten, sollte das Problem in kleinere Teilprobleme zerlegt werden. Zuerst müssen wir eine Liste aller Elemente y mit y * y < = x:

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

Dann müssen wir die Elemente nur die x teilen:

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

Dann müssen wir, wenn diese Liste überprüfen leer ist:

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

Und wenn Ihnen das lispy aussieht, mit $

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

0 einige der Pars ersetzen

Für zusätzliche Klarheit können Sie "auslagern", um die Lambda-Ausdrücke:

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

Sie können es machen fast "human readable" von null $ Filterwechsel mit jeder nicht $:

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

Answer 2

1. Da sqrt hat den Typ Floating a => a -> a. Dies bedeutet, dass der Eingang ein Floating Typ sein muss und der Ausgang vom selben Typ sein wird. Mit anderen Worten, x muss ein Floating Typ sein. Sie haben jedoch x als Integer deklariert, was kein Floating Typ ist. Außerdem benötigt floor einen RealFrac Typ, also muss x auch so sein.

   Die Fehlermeldung deutet darauf hin, dass Sie beheben, dass, indem sie Integer ein Floating Typ (durch eine Instanz definieren Floating Integer (und das gleiche für RealFrac).

   Natürlich dieses in diesem Fall nicht der richtige Ansatz ist. Sie Rather sollte fromIntegral verwenden x zu einem Real zu konvertieren (die eine Instanz von Floating und RealFrac ist) und dann das zu sqrt geben.

2. Ja. Sobald == sieht, dass der rechte Operand hat ein t mindestens ein Element, es weiß, es ist nicht gleich [] und gibt somit False zurück.

   Das heißt, null ist eine idiomatische Möglichkeit zu überprüfen, ob eine Liste leer ist als [] ==.

Answer 3

In Bezug auf den zweiten Punkt, stoppt er, zum Beispiel:

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

Returns False

Answer 4

1. denke ich WinHugs muss ein Modul für Integer importieren und etc ... Versuchen Int
2. Der Interpreter berechnet nichts, bis Sie zB anrufen isPrime 32 dann wird es den Ausdruck faul berechnen.

PS Ihre isPrime-Implementierung ist nicht die beste Implementierung!

Answer 5

Landei-Lösung ist groß, aber wenn Sie eine efficient¹ Implementierung wollen, müssen wir (dank 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 

Die ‚Effizienz‘ kommt f von der Verwendung von konstanten Primzahlen. Es verbessert die Suche auf zwei Arten:

1. Die Haskell-Laufzeit, die Ergebnisse so nachfolgende Anrufungen ausgewertet werden nicht
cachen könnte
2. Es beseitigt eine Reihe von Zahlen, die durch Logik Kenntnis, dass der sieve Wert ist einfach eine rekursive Tabelle, wo sagt der Kopf von die Liste ist prime, und fügt es hinzu. Für den Rest der Listen, wenn kein anderer Wert bereits in der Liste vorhanden ist, die die Nummer bildet, ist auch seine Primzahl possible Liste aller möglichen Primzahlen, da alle möglichen Primzahlen in der Form 6 * k-1 oder 6 sind * k-1, außer daß 2 und 3 Die gleiche Regel auch für shortCircuit angewendet wird, um schnell

Fußnote durch DF von Berechnungen bürgen
¹ Es ist immer noch eine schrecklich ineffiziente Art, Primzahlen zu finden. Verwenden Sie keine Probenteilung, wenn Sie Primzahlen größer als ein paar Tausend benötigen, verwenden Sie stattdessen ein Sieb. Es gibt mehrere far moreefficient Implementierungen auf hackage.