Ich habe eine unendliche Liste und möchte ein Paar (a,b) auswählen, wobei a und b beide aus der Liste kommen und das Paar eine Eigenschaft erfüllt. Die Verwendung von List Comprehensions scheint nicht zu funktionieren, da die Liste unendlich ist.
Ich versuche ein Paar Primzahlen zu finden, die sich zu einer bestimmten Zahl addieren (siehe dieses Codegolfproblem <) / a>).
Ich habe primes definiert, was eine unendliche Liste von Primzahlen ist, aber wenn ich naiv versuche, ein Paar Primzahlen wie unten zu wählen, endet der Prozess nie.
Mir ist klar, dass die Liste der generierten Primzahlen [(2,2), (2,3), (2,5)...] ist. Grundsätzlich wird a zum ersten Element von primes und sobald b erschöpft ist, wird es auf das zweite Element verschoben. Weil primes unendlich ist, wird es niemals erschöpft sein!
Gibt es eine einfache Möglichkeit, List Comprehensions zu verwenden, um dieses Problem zu lösen? Gelingt das nicht, gibt es eine einfache Lösung?
Der schönste Weg ist die Breite . erste Liste Monade . Da List Comprehensions nur als syntaktischer Zucker der Monade betrachtet werden kann (ähnlich wie do ), ermöglicht es Ihnen, es genau so aussehen zu lassen, wie Sie es jetzt haben:
Es ist schade, dass Sie @ leftaroundabouts Lösung nicht akzeptiert haben. Es hat viel mehr zu bieten. Zum Beispiel hat die andere Lösung eine Heuristik "alle Zahlen müssen kleiner als n sein" (was tun Sie für Probleme, bei denen Sie diese Heuristik nicht haben?), Und ein paar andere Schritte, die es schwerer machen, das tatsächlich zu beweisen ist eine Lösung für Goldbachs Problem - z Können Sie demonstrieren, dass die Aufzählung der Primzahlen alle nützlichen Primzahlpaare zusammenfasst? (Es tut, aber können Sie es demonstrieren? Dies ist die Schwäche dieser Lösung)
Hier werde ich zeigen, wie Sie die Lösung @leftaroundabout präsentieren können, ohne das Wort "monad" zu sagen.
Das Problem mit dem Listenverständnis, das Sie zuerst erstellt haben, ist, dass es die Lösung "Tiefe zuerst" durchsucht - nehmen Sie ein Element aus der ersten Liste und versuchen Sie dann alle Kombinationen mit diesem Element. Wenn es jedoch eine unendliche Anzahl von Kombinationen gibt, werden Sie niemals Paare mit dem zweiten Element aus der ersten Liste aufzählen. Hier müssen wir über "Breite zuerst" nach Lösungen suchen.
Nehmen wir an, gen ist ein Generator von Lösungen:
Nehmen wir an, gens ist ein Generator von Generatoren von Lösungen:
Alles, was wir jetzt tun müssen, ist Lösungen aufzuzählen, indem wir jeweils eine Lösung von jedem Generator nehmen. Wohlgemerkt, wenn die Anzahl der Generatoren unendlich ist, können wir sie nicht einfach einzeln nehmen - so werden wir niemals die zweite Lösung vom ersten Generator bekommen, also müssen wir sie irgendwie "schreiten":
%Vor%Das ist es.
%Vor% Jetzt zur Effizienz. Es ist alles in gens und gen . Fügen Sie eine Bedingung zu gens zu takeWhile ((<=n) . (x+)) hinzu, und es funktioniert auch dann, wenn Goldbachs Vermutung falsch ist (Sie müssen sie jedoch nicht hinzufügen). Fügen Sie eine Bedingung zu gen zu takeWhile (<=x) hinzu, und Sie werden nur die Paare aufzählen, in denen die erste Primzahl größer als die andere ist.
Tags und Links haskell functional-programming lazy-evaluation