Haskell-Prime-Test

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 ein Floating, z. indem Sie sqrt (fromIntegral x)

2) Ich sehe keinen Grund, warum == nicht faul sein sollte, aber zum Testen auf eine leere Sammlung können Sie die Funktion null verwenden (was definitiv faul ist, da sie auf unendlichen Listen funktioniert):

Aber um eine idiomatische Lösung zu erhalten, sollten Sie das Problem in kleinere Teilprobleme aufteilen. Zuerst benötigen wir eine Liste aller Elemente y mit y * y & lt; = x:

Dann brauchen wir nur die Elemente, die x teilen:

Dann müssen wir prüfen, ob diese Liste leer ist:

Und wenn Ihnen das lispy erscheint, ersetzen Sie einige der Parens durch $

Für zusätzliche Klarheit können Sie die Lambdas "outsourcen":

Sie können es fast "menschenlesbar" machen, indem Sie null $ filter durch nicht $ any ersetzen:

1. Weil sqrt den Typ Floating a => a -> a hat. Dies bedeutet, dass die Eingabe ein Floating -Typ sein muss und die Ausgabe vom selben Typ ist. Mit anderen Worten, x muss ein Floating -Typ sein. Sie haben jedoch x vom Typ Integer angegeben, was kein Floating -Typ ist. Außerdem benötigt floor einen RealFrac Typ, also muss auch x das sein.

   Die Fehlermeldung weist darauf hin, dass Sie das beheben, indem Sie Integer a Floating type angeben (indem Sie eine Instanz Floating Integer definieren (und dasselbe für RealFrac ).

   Natürlich ist das in diesem Fall nicht der richtige Ansatz. Stattdessen sollten Sie fromIntegral verwenden, um x in ein Real zu konvertieren (was eine Instanz von Floating und RealFrac ist), und dann an sqrt .

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

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

Die Lösung von Landei ist großartig, aber wenn Sie eine effizientere Implementierung wünschen, haben wir (dank BMeph):

Die "Effizienz" kommt von der Verwendung konstanter Primzahlen. Es verbessert die Suche auf zwei Arten:

1. Die Haskell-Laufzeit konnte die Ergebnisse zwischenspeichern, damit nachfolgende Aufrufe nicht ausgewertet werden
2. Es eliminiert eine Reihe von Zahlen nach Logik Beachten Sie, dass der Wert sieve einfach eine rekursive Tabelle ist, in der der Kopf von Die Liste ist prime und fügt sie hinzu. Für den Rest der Listen, wenn es keine gibt anderen Wert bereits in der Liste, die die Zahl dann seine Primzahl zusammensetzt possible ist eine Liste aller möglichen Primzahlen, da alle möglichen Primzahlen in der Form 6 * k-1 oder 6 * k-1 außer 2 und 3 Die gleiche Regel wird auch für shortCircuit angewendet, um schnell aus den Berechnungen herauszukommen

Fußnote von D.F. ¹ 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 weit mehr effizient Implementierungen auf hackage .