Warum "und" auf einer leeren Liste wahr zurückgibt, impliziert das, dass eine leere Liste True enthält? Tut mir leid, aber ich kann das nicht richtig lesen und verstehen, also korrigiert mich bitte. Danke.
%Vor% In der Mathematik ist es oft nützlich, über eine binäre Operation zu sprechen, z. B. && , || , + , * , usw. mit einer Identität . Die Identität ist ein Wert e , so dass die folgende Eigenschaft für eine generische Binäroperation <>
Für die oben aufgeführten Operatoren sind sie kommutativ , was x <> y = y <> x für alle x und y bedeutet, also müssen wir nur eine der obigen Eigenschaften überprüfen. Für and ist der fragliche binäre Operator && und für or ist der binäre Operator || . Wenn wir für diese Operationen eine Cayley-Tabelle erstellen, sieht das wie
Wie Sie sehen können, ist für && , wenn Sie True && False und True && True haben, die Antwort immer das zweite Argument von && . Für || , wenn Sie False || False und False || True haben, ist die Antwort immer das zweite Argument, also muss das erste Argument von jedem das Identitätselement unter diesen Operatoren sein. Einfach gesagt:
Daher ist die bevorzugte Antwort, wenn keine Elemente zum Ausführen des Operators vorhanden sind, das Identitätselement für jede Operation.
Es kann hilfreich sein, auch über die Identitätselemente für + und * nachzudenken, die 0 bzw. 1 sind:
Sie können dies auch auf Operationen wie Listenverkettung ( ++ mit [] ), Funktionszusammensetzung für Funktionen vom Typ a -> a ( (.) mit id ) und viele andere erweitern. Da dies anfängt, wie ein Muster zu wirken, könnten Sie fragen, ob dies in Haskell bereits eine Sache ist, und tatsächlich ist es das. Das Modul Data.Monoid definiert die Typklasse Monoid , die dieses Muster abstrahiert, und seine minimale Definition ist
Und es hat sogar Aliase mappend als <> für die Benutzerfreundlichkeit (es war kein Zufall, dass ich es oben für einen generischen binären Operator gewählt habe). Ich ermutige Sie, dieses Modul anzusehen und mit seinen Definitionen herumzuspielen. Der Quellcode ist ziemlich einfach zu lesen und erleuchtet.
and und or sind nur Falten, und eine Falte, die in einer leeren Liste aufgerufen wird, erzeugt ihr Startargument, das True bzw. False ist.
Sie werden nur dann mit einer Faltung implementiert, wenn Prelude geladen ist, andernfalls werden sie mit expliziter Rekursion realisiert, was an sich noch immer eine Falte ist, obwohl foldr oder foldl nicht verwendet wird. Sie verhalten sich immer noch so, wie wir sehen können, indem wir die Quelle untersuchen:
Hier ist ein Link zu den Implementierungen .
Um die Verwirrung in den Kommentaren zu beseitigen: Eine Falte ist eine Funktion, die eine binäre Funktion und einen Startwert (oft Akkumulator genannt) annimmt und eine Liste durchläuft, bis sie leer ist. Wenn eine leere Liste aufgerufen wird, gibt die Faltung den Akkumulator zurück, so wie es ist, wenn es keine Rolle spielt, ob die Liste bereits durchlaufen wurde oder nicht. Dies ist eine Beispielimplementierung von foldr :
and ist einfach
wodurch and [] zu True ausgewertet wird.
Zusätzlich zur @bheklilr-Antwort sollten wir uns daran erinnern, dass ein Monoid ein Tupel (M,e,<>) ist, wobei M ein Objekt ist (Sie können es sich als Typ vorstellen), e ist ein Punkt des Objekts M ( e : M - Element des Typs) und <> ist eine binäre Operation, die assoziativ ist und e als Identität hat:
Es gibt Monoid-Homomorphismen zwischen einigen Monoiden. Es gibt ein freies Monoid - das Monoid, aus dem ein Homomorphismus in ein anderes besteht. Ein solches freies Monoid ist eine Liste: ([a], [], ++) kann in jedes andere Monoid abgebildet werden. Zum Beispiel:
Dann sind sum , product , and , or die jeweiligen monoiden Homomorphismen und bilden die Elemente der Typen [Int] und [Bool] ab. Bei der Definition des Monoid-Homomorphismus wird das Mapping h der Monoide so durchgeführt, dass eine beliebige Liste x++y in den Punkt h(x ++ y) == (h x) <> (h y) abgebildet wird - zum Beispiel and (x++[]) == (and x) && (and []) . Aus letzterem Beispiel wird deutlich, dass seit x++[] == x , also (and x) && (and []) == and x also and [] in das Identity-Element von (Bool, True, &&) mappt.
Ausgezeichnete Antworten, aber ich denke, es ist eine intuitivere Behandlung wert. Anstelle von and :: [Bool] -> Bool schauen wir uns jedoch all :: (a -> Bool) -> [Bool] -> Bool an. Sie können auf diese Weise an all denken. Stellen Sie das Prädikat (das Argument a -> Bool ) als Hypothese über Listenelemente dar. Dann liefert all False genau dann zurück, wenn die Liste mindestens ein Gegenbeispiel für die Hypothese enthält. Wenn die Liste leer ist, gibt es keine Gegenbeispiele, also ist es trivial bestätigt.
Um es wieder in and zu bringen, beachten Sie, dass and und all interdefinierbar sind. Wenn Sie and haben, können Sie all auf diese Weise definieren:
Und umgekehrt, wenn Sie bereits all hätten, könnten Sie and daraus definieren:
Eine Möglichkeit, über True und False nachzudenken, sind Elemente des Gitters , geordnet nach False < True . && und || können als binäre Operationen "meet" (größte untere Grenze) und "Join" (kleinste obere Grenze) für dieses Gitter angesehen werden. In ähnlicher Weise sind and und or allgemeine endliche Treffen und endliche Join-Operationen. Was ist and [] ? Es ist die größte untere Grenze von [] . Aber True ist (leer) kleiner oder gleich jedem Element von [] , also ist es eine untere Grenze von [] , und (natürlich) ist es größer als jede andere untere Grenze (die andere ist False ) , also and [] = True . Die algebraische Ansicht (das Denken über Monoide und so) entpuppt sich als völlig äquivalent zur Ordnungstheorie, aber ich denke, die Ordnungstheorie bietet mehr visuelle Intuition.
Die Logik von and ist es, den ersten Eintrag in der Liste zu finden, der False ist. Wenn der Eintrag nicht gefunden wird, lautet das Ergebnis True . Zum Beispiel:
durchläuft nicht die gesamte unendliche Liste, sondern stoppt bei 3 und gibt False zurück. Es gibt kein False -Element in der leeren Liste, daher verwenden wir standardmäßig True .
Für or ist es ähnlich: es versucht das erste True zu finden und stoppt dann, andernfalls ist es False .