Frage Haskell lernen: Scheinbar zirkuläres Programm - bitte helfen Sie zu erklären


Ich gehe gerade durch das Buch "The Haskell Road to Logic, Mathe und Programming" von Doets und Van Eijck. Ich habe noch nie eine funktionale Programmiersprache bis zu diesem Buch kennengelernt, also behalte das im Hinterkopf.

Noch früh im Buch gibt es den folgenden Code für einen Primzahltest:

ldp :: Integer -> Integer
ldp n = ldpf primes1 n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p 
              | p^2 > n      = n
              | otherwise    = ldpf ps n

primes1 :: [Integer]
primes1 = 2 : filter prime [3..]

prime :: Integer -> Bool
prime n | n < 1     = error "not a positive integer"
        | n == 1    = False 
        | otherwise = ldp n == n

Es gibt eine scheinbar zirkuläre Programmierung, die darin besteht, dass ldp primes1 aufruft, das prime aufruft, das wiederum ldp aufruft. Während das Buch dies als eine Erklärung anbietet, warum das Programm ausgeführt und beendet wird:

ldp ruft primes1, die Liste der Primzahlen, auf. Dies ist eine erste Illustration einer "faulen Liste". Die Liste wird "faul" genannt, weil wir nur den Teil der Liste berechnen, den wir für die weitere Verarbeitung benötigen. Um primes1 zu definieren, brauchen wir einen Test auf Primalität, aber dieser Test ist selbst definiert in Bezug auf die Funktion LD, die sich wiederum auf primes1 bezieht. Wir scheinen im Kreis herumzurennen. Dieser Kreis kann nicht bösartig gemacht werden, indem man den Primzahltest für 2 vermeidet. Wenn es gegeben ist, dass 2 Primzahl ist, dann können wir die Primzahl von 2 in der LD-Prüfung verwenden, dass 3 Primzahl ist, und so weiter, und wir sind oben und läuft

Während ich denke, dass ich diese Erklärung verstehe, würde ich es sehr schätzen, wenn jemand in Laien erklären könnte:

  1. Was für eine "faule Liste" ist und wie sie in diesem Zusammenhang gilt?
  2. Wie zu wissen, dass 2 Prime ist, erlaubt das Programm nicht bösartig?

Alle Antworten werden sehr geschätzt.


9
2017-08-17 19:42


Ursprung


Antworten:


Das Erste, was zu beachten ist, ist, dass dieser Code alleine nichts tut. Es ist nur ein Haufen mathematischer Ausdrücke und es ist egal, wie zirkular es ist, bis wir versuchen, einige Werte daraus zu extrahieren. Wie machen wir das?

Wir könnten:

print $ take 1 primes1

Das ist kein Problem. Wir können den ersten Wert von primes1 nehmen, ohne den rekursiven Code zu betrachten, er ist explizit dort als 2. Was ist mit:

print $ take 3 primes1

Lass uns versuchen, zu erweitern primes1 um einige Werte heraus zu bekommen. Um diese zu behalten Ausdrücke beherrschbar, ich ignoriere jetzt die print und take Teile, aber Erinnere dich daran, dass wir diese Arbeit nur wegen ihnen machen. primes1 ist:

primes1 = 2 : filter prime [3..]

Wir haben unseren ersten Wert und der erste Schritt zu unserem zweiten ist der erweiterte Filter. Wenn dies eine strenge Sprache wäre, würden wir zuerst versuchen [3 ..] zu erweitern und zu bekommen stecken. Eine mögliche Definition von Filter ist:

filter f (x:xs) = if f x then x : filter f xs else filter f xs

was gibt:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..]

Unser nächster Schritt muss herausfinden, ob prime 3 ist wahr oder falsch, also lasst uns erweitern Sie es mit unseren Definitionen von prime, ldp und ldpf.

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

Jetzt werden die Dinge interessant, primes1 referenziert sich selbst und ldpf benötigt den ersten Wert um seine Berechnung zu machen. Glücklicherweise können wir den ersten Wert leicht erhalten.

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

Jetzt wenden wir die Guard-Klauseln in ldpf an und finden 2^2 > 3, deshalb ldpf (2 : tail primes) 3 = 3.

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : 3 : filter prime [4..] 

Wir haben jetzt unseren zweiten Wert. Beachten Sie, dass die rechte Seite unserer Auswertung nie besonders groß wurde und dass wir der rekursiven Schleife nie sehr weit folgen mussten.

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..]

Wir verwenden die Wächterklausel rem 4 2 == 0deshalb bekommen wir 2 hier.

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : filter prime [5..]
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

Keine Wache passt, also rekrutieren wir:

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

Jetzt 3^2 > 5 so dass der Ausdruck 5 ist.

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : 5 : filter prime [6..]

Wir brauchen nur drei Werte, damit die Auswertung stoppen kann.

So, jetzt, um deine Fragen zu beantworten. Eine faule Liste ist eine, die nur erfordert, dass wir auswerten, was wir brauchen, und Die 2 hilft, weil es sicherstellt, dass wir immer dann, wenn wir den rekursiven Schritt erreichen, genug Werte haben berechnet. (Stellen wir uns vor, wir erweitern diesen Ausdruck, wenn wir die 2 nicht kennen würden, würden wir in einer schönen Schleife enden schnell.)


9
2017-08-18 08:52



In Ordnung:

Faulheit ist die Eigenschaft, Ausdrücke nur so zu bewerten, wie Sie es brauchen, und nicht wann Sie es könnten. Eine faule Liste ist eine, die möglicherweise unendlich sein könnte. Offensichtlich wäre der Versuch, eine unendliche Liste zu bewerten, eine schlechte Idee, wenn die Bewertung nicht faul wäre.

Ich bin mir nicht sicher, was "nicht-bösartig" bedeutet, aber ich denke, Sie werden feststellen, dass das Vorhandensein des Wertes "2" als eine bekannte Primzahl einen ergibt Basisfall für die Rekursion, d. h. es stellt eine bestimmte Eingabe bereit, auf der das Programm endet. Das Schreiben einer rekursiven Funktion (oder tatsächlich eines Satzes von wechselseitig rekursiven Funktionen) beinhaltet gewöhnlich das Reduzieren eines Eingabewertes in diesem Basisfall in aufeinanderfolgenden Anwendungsschritten.

Als Referenz werden Programmfragmente dieser Form üblicherweise aufgerufen gegenseitig rekursiv. Der Begriff "Zirkelbezug" wird in diesem Fall nicht wirklich verwendet.


6
2017-08-17 19:51



Ein charakteristisches Merkmal von Haskell ist seine Faulheit. Listen sind nur ein Teil dieser Geschichte. Grundsätzlich tritt Haskell nie auf irgendein Berechnung bis:

  1. der Wert der Berechnung ist erforderlich um etwas anderes zu berechnen, das ist erforderlich zu...
  2. Sie haben Haskell angewiesen, etwas früher zu berechnen, als es sonst möglich wäre.

Also die primes1 Funktion erzeugt eine Liste von Integer Werte, aber es erzeugt nicht mehr als notwendig ist, um die Gesamtberechnung zu erfüllen. Trotzdem, wenn Sie es so definiert haben:

primes1 :: [Integer]
primes1 = filter prime [2..]

Du hättest ein Problem. primes1 würde versuchen, den ersten Wert in seiner Sequenz durch (indirektes) Auswerten zu erzeugen prime 2, die bewerten würde ldp 2, die nach dem ersten von primes1... presto Endlosschleife!

Durch direkte Rückgabe von 2 als ersten Wert der von primes1, vermeiden Sie die Endlosschleife. Für jeden nachfolgenden Wert, der in der Sequenz generiert wird, primes1 hat bereits einen vorherigen Wert generiert, der von ausgewertet wird ldp als Teil der Berechnung des nachfolgenden Wertes.


3
2017-08-17 20:06