Effizienz der Gleichheit in Haskell

Question

Ich habe eine Funktion, die Daten nimmt und entweder die gleichen Daten oder eine leicht modifizierte Version zurückgibt.

Ich möchte mein Programm eine Sache machen lassen, wenn es sich geändert hat oder eine andere Sache, wenn es sich nicht geändert hat.

Zuvor habe ich ein Paar (Bool,Object) zurückgegeben und verwendet, um zu überprüfen, ob es sich geändert hat. In letzter Zeit fiel mir ein, dass ich den Code vereinfachen könnte, indem ich einfach das Objekt zurücksende und die Gleichheit mit == überprüfe.

Aber dann erkannte ich, dass Haskell nicht zwischen tiefer Gleichheitsprüfung und "Objektidentität" (d. H. Zeigergleichheit) unterscheidet. Wie kann ich also wissen, ob die Verwendung von == effizient ist oder nicht? Sollte ich es aus Effizienzgründen vermeiden oder gibt es Fälle, in denen ich mich darauf verlassen kann, dass der Compiler herausfindet, dass er keine tiefe Gleichheitsprüfung durchführen muss?

Normalerweise wäre ich nicht allzu besorgt über die Effizienz beim Schreiben eines ersten Programms, aber dies betrifft die Schnittstelle zu meinem Modul, also möchte ich es richtig machen, bevor zu viel Code geschrieben, und es scheint nicht wert zu sein Machen Sie das Programm viel weniger effizient, nur um ein kleines Stück Code. Außerdem möchte ich eine bessere Vorstellung davon bekommen, auf welche Art von Optimierungen ich mich verlassen kann.

Answer 1

Es ist immer eine schlechte Idee, sich auf unsichere Compiler-Optimierungen zu verlassen, um eine so wichtige Leistungsgarantie wie Gleichzeitigkeit in konstanter Zeit und tiefe Gleichzeitigkeit in linearer Zeit zu bieten. Sie sind viel besser dran mit einem neuen Typ, der einen Wert plus Informationen darüber enthält, ob der Wert neu ist.

data Changed a = Changed a | Unchanged a 

oder

data Changed a = Changed a | Unchanged 

Wir verwenden tatsächlich eine ähnliche Art innerhalb der Glasgow Haskell Compiler Je nach Anwendung kann dies entweder so können wir laufen den Optimierer halten, bis der Code zu ändern aufhört. Wir führen auch eine iterative Datenflussanalyse durch, bis sich die Ergebnisse nicht mehr ändern.

Wir fanden es nützlich, diesen Typ eine Monade zu machen, so dass wir einige einfache Funktionen höherer Ordnung mit do Notation schreiben können, aber es ist nicht notwendig — nur eine Bequemlichkeit.

Zusammenfassung: Wenn Sie konstant Zeit überprüft, Code it yourself — nicht auf einer möglichen Compiler-Optimierung verlassen, die es nicht — sein könnten oder die in der nächsten Version ändern kann.

Answer 2

Ich bin immer noch ein relativer Haskell Noob, also nimm meine Antwort mit einem Gran Salz, und bitte vergib mir, wenn meine Antwort nicht so direkt ist, wie es sein sollte!

In Haskell, Betreiber sind nicht speziell - sie sind nur Infix-Funktionen.

Sie können die definition of the equality operator selbst in der Standardvorspiel betrachten.

Natürlich kann es überladen werden, um mit dem von Ihnen definierten Datentyp zu arbeiten - aber wenn Sie das Überladen tun, werden Sie wissen, wie effizient die Implementierung ist.

Es kann hilfreich sein zu wissen, dass Sie Hoogle verwenden können, um die gewünschte Funktionsdefinition zu finden. So habe ich die Definition des Gleichheitsoperators gefunden.

Answer 3

Der abgeleitete (==) ist immer tief Vergleich. Ihre Frage war discussed auf Haskell-Cafe.