Wo und warum sollte ich extra leere Muster verwenden?

8

Zum Beispiel:

%Vor%

Es gibt zusätzliche Muster für [] und es sieht so aus, als ob sie in Haskell Data.List verwendet werden, aber welche Art von Optimierung ist das? Und wo ist der Unterschied zu Idris hier?

Ich frage, weil ich gehört habe, dass "es das Nachdenken darüber schwieriger machen wird" und die Person, die mich sagte, die keine Zeit hatte, es vollständig zu erklären.

Ich bezweifle, dass ich es verstehen kann, wenn ich "den Beweis" der Funktion reduziere.

Darf mir jemand aus den Positionen von Haskell und Idris die Politik der zusätzlichen Muster erklären, damit ich den Unterschied verstehen und sehen kann.

    
Маша 22.04.2015, 09:36
quelle

4 Antworten

13

Semantisch gesprochen, das Muster

%Vor%

sieht sogar vom Standpunkt der Leistung aus redundant aus. Stattdessen in Haskell

%Vor%

ist nicht redundant, da es sonst

ist %Vor%

würde divergieren, da das Verständnis versuchen würde, alle Elemente x <- [0..] auszuprobieren.

Ich bin mir nicht sicher, ob mir dieser Sonderfall gefällt. Warum sollten wir keinen speziellen Fall hinzufügen, der intersectBy (==) [0..] [2] abdeckt, sodass% ce_de% zurückgegeben wird? Wenn es um die Leistung geht, möchte ich in vielen Fällen einen O (n log n) -Ansatz durch Vorsortierung verwenden, auch wenn dies nicht für unendliche Listen funktioniert und [2] erfordert.

    
chi 22.04.2015, 09:47
quelle
11

Sie müssen nicht raten, wann Sie den Verlauf über git blame , GHC Trac und die Mailingliste der Bibliotheken einsehen können.

Ursprünglich war die Definition nur die dritte Gleichung,

%Vor%

In Ссылка wurde die zweite Gleichung als Strenge / Leistungsverbesserung hinzugefügt, und zur gleichen Zeit, die Die erste Gleichung wurde hinzugefügt, um die neue Definition immer mindestens so zu definieren wie das Original. Andernfalls wäre intersectBy f [] _|_ _|_ , wenn es zuvor [] gewesen wäre.

Es scheint mir, dass diese aktuelle Definition jetzt maximal faul ist: Sie ist für alle Eingaben so definiert wie möglich, außer dass man wählen muss, ob man zuerst die linke oder die rechte Liste auf Leerheit prüfen soll. (Und, wie ich oben erwähnte, wird diese Wahl getroffen, um mit der historischen Definition übereinzustimmen.)

    
Reid Barton 22.04.2015 22:14
quelle
5

@chi erklärt den Fall _ _ [] , aber _ [] _ erfüllt auch einen Zweck: Es bestimmt, wie intersectBy behandelt bottom . Mit der Definition wie geschrieben:

%Vor%

Entfernen Sie das erste Muster und es wird:

%Vor%

Ich bin mir nicht 100% sicher, aber ich glaube, es gibt auch einen Leistungsvorteil, wenn man im ersten Muster nichts bindet. Das endgültige Muster ergibt das gleiche Ergebnis für xs == [] ohne Auswertung eq oder ys , aber AFAIK es immer noch reserviert Stapelspeicher für ihre Thunks.

    
Theodore Lief Gannon 22.04.2015 21:55
quelle
4

There ist ein großer Unterschied in Idris: Idris-Listen sind immer endlich! Außerdem ist Idris eine meist strenge (call-by-value) Sprache und verwendet optional einen Totalitätsprüfer, so dass es ziemlich vernünftig ist anzunehmen, dass in den Argumentenlisten keine Unterseiten versteckt sein werden. Die Bedeutung dieses Unterschieds besteht darin, dass die beiden Definitionen bei Idris wesentlich semantisch identischer sind als bei Haskell. Die Auswahl, die getroffen werden soll, kann basierend auf der Leichtigkeit getroffen werden, Eigenschaften der Funktion nachzuweisen, oder kann auf Einfachheit basieren.

    
dfeuer 24.04.2015 03:49
quelle

Tags und Links