Warum ist eine verzögerte Bewertung nützlich?

119

Ich habe mich lange gefragt, warum eine faule Bewertung nützlich ist. Ich muss mir noch jemanden erklären lassen, der Sinn macht. Meistens läuft es darauf hinaus, "mir zu vertrauen".

Hinweis: Ich meine nicht Memoisierung.

Joel McCracken
quelle

Antworten:

96

Meistens, weil es effizienter sein kann - Werte müssen nicht berechnet werden, wenn sie nicht verwendet werden sollen. Zum Beispiel kann ich drei Werte an eine Funktion übergeben, aber abhängig von der Reihenfolge der bedingten Ausdrücke kann tatsächlich nur eine Teilmenge verwendet werden. In einer Sprache wie C würden sowieso alle drei Werte berechnet; In Haskell werden jedoch nur die erforderlichen Werte berechnet.

Es erlaubt auch coole Sachen wie unendliche Listen. Ich kann keine unendliche Liste in einer Sprache wie C haben, aber in Haskell ist das kein Problem. Unendliche Listen werden in bestimmten Bereichen der Mathematik ziemlich häufig verwendet, daher kann es nützlich sein, sie manipulieren zu können.

Mipadi
quelle
6
Python hat unendlich viele Listen über Iteratoren träge ausgewertet
Mark Cidade
4
Sie können eine unendliche Liste in Python mithilfe von Generatoren und Generatorausdrücken emulieren (die ähnlich wie ein Listenverständnis funktionieren
John Montgomery
24
Generatoren machen Lazy-Listen in Python einfach, aber andere Lazy-Evaluationstechniken und Datenstrukturen sind merklich weniger elegant.
Peter Burns
3
Ich fürchte, ich würde dieser Antwort nicht zustimmen. Früher dachte ich, dass es bei Faulheit um Effizienz geht, aber nachdem ich Haskell in erheblichem Umfang verwendet und dann zu Scala gewechselt und die Erfahrung verglichen habe, muss ich sagen, dass Faulheit aufgrund der Effizienz oft, aber selten wichtig ist. Ich denke, Edward Kmett trifft die wahren Gründe.
Owen
3
Ich bin ebenfalls anderer Meinung, obwohl es in C aufgrund der strengen Bewertung keine explizite Vorstellung von einer unendlichen Liste gibt, können Sie den gleichen Streich in jeder anderen Sprache (und in der Tat in den meisten tatsächlichen Implementierungen jeder faulen Sprache) leicht spielen, indem Sie Thunks verwenden und Funktionen weitergeben Zeiger, um mit einem endlichen Präfix der unendlichen Struktur zu arbeiten, die durch ähnliche Ausdrücke erzeugt wird.
Kristopher Micinski
71

Ein nützliches Beispiel für eine verzögerte Bewertung ist die Verwendung von quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Wenn wir jetzt das Minimum der Liste finden wollen, können wir definieren

minimum ls = head (quickSort ls)

Welches sortiert zuerst die Liste und nimmt dann das erste Element der Liste. Aufgrund der verzögerten Auswertung wird jedoch nur der Kopf berechnet. Wenn wir beispielsweise das Minimum der Liste [2, 1, 3,]nehmen, filtert quickSort zuerst alle Elemente heraus, die kleiner als zwei sind. Dann macht es quickSort (Rückgabe der Singleton-Liste [1]), was bereits ausreicht. Aufgrund der verzögerten Auswertung wird der Rest nie sortiert, was viel Rechenzeit spart.

Dies ist natürlich ein sehr einfaches Beispiel, aber Faulheit funktioniert genauso für Programme, die sehr groß sind.

All dies hat jedoch einen Nachteil: Es wird schwieriger, die Laufzeitgeschwindigkeit und die Speichernutzung Ihres Programms vorherzusagen. Dies bedeutet nicht, dass faule Programme langsamer sind oder mehr Speicher benötigen, aber es ist gut zu wissen.

Chris Eidhof
quelle
19
Im Allgemeinen take k $ quicksort listdauert nur O (n + k log k) Zeit, wobei n = length list. Bei einer nicht faulen Vergleichssortierung würde dies immer O (n log n) Zeit in Anspruch nehmen.
Ephemient
@phemient meinst du nicht O (nk log k)?
MaiaVictor
1
@ Viclib Nein, ich meinte was ich sagte.
Ephemient
@ Ephemient dann denke ich, ich verstehe es leider nicht
MaiaVictor
2
@Viclib Ein Auswahlalgorithmus zum Finden der obersten k Elemente aus n ist O (n + k log k). Wenn Sie Quicksort in einer faulen Sprache implementieren und diese nur so weit auswerten, dass die ersten k Elemente ermittelt werden (die Auswertung wird danach gestoppt), werden genau dieselben Vergleiche durchgeführt wie bei einem nicht faulen Auswahlalgorithmus.
Ephemient
70

Ich finde eine faule Bewertung für eine Reihe von Dingen nützlich.

Erstens sind alle vorhandenen faulen Sprachen rein, da es sehr schwierig ist, über Nebenwirkungen in einer faulen Sprache nachzudenken.

Mit reinen Sprachen können Sie über Funktionsdefinitionen mithilfe von Gleichungsargumenten nachdenken.

foo x = x + 3

Leider werden in einer nicht faulen Umgebung nicht mehr Anweisungen zurückgegeben als in einer faulen Umgebung, sodass dies in Sprachen wie ML weniger nützlich ist. Aber in einer faulen Sprache können Sie sicher über Gleichheit argumentieren.

Zweitens werden viele Dinge wie die 'Wertbeschränkung' in ML in faulen Sprachen wie Haskell nicht benötigt. Dies führt zu einer starken Entschlüsselung der Syntax. ML-ähnliche Sprachen müssen Schlüsselwörter wie var oder fun verwenden. In Haskell fallen diese Dinge auf einen Begriff zusammen.

Drittens können Sie mit Faulheit sehr funktionalen Code schreiben, der in Teilen verstanden werden kann. In Haskell ist es üblich, einen Funktionskörper wie folgt zu schreiben:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Auf diese Weise können Sie von oben nach unten arbeiten, obwohl Sie den Körper einer Funktion verstehen. ML-ähnliche Sprachen zwingen Sie dazu, eine Sprache zu verwenden let, die streng bewertet wird. Folglich wagen Sie es nicht, die let-Klausel auf den Hauptteil der Funktion zu übertragen, denn wenn sie teuer ist (oder Nebenwirkungen hat), möchten Sie nicht, dass sie immer ausgewertet wird. Haskell kann die Details der where-Klausel explizit "verschieben", da es weiß, dass der Inhalt dieser Klausel nur nach Bedarf ausgewertet wird.

In der Praxis tendieren wir dazu, Wachen zu verwenden und diese weiter zusammenzubrechen, um:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Viertens bietet Faulheit manchmal einen viel eleganteren Ausdruck bestimmter Algorithmen. Eine faule "schnelle Sortierung" in Haskell ist ein Einzeiler und hat den Vorteil, dass Sie, wenn Sie nur die ersten Artikel betrachten, nur Kosten zahlen, die proportional zu den Kosten für die Auswahl nur dieser Artikel sind. Nichts hindert Sie daran, dies strikt zu tun, aber Sie müssten den Algorithmus wahrscheinlich jedes Mal neu codieren, um die gleiche asymptotische Leistung zu erzielen.

Fünftens können Sie mit Faulheit neue Kontrollstrukturen in der Sprache definieren. Sie können kein neues 'wenn .. dann .. sonst ..' wie Konstrukt in einer strengen Sprache schreiben. Wenn Sie versuchen, eine Funktion wie folgt zu definieren:

if' True x y = x
if' False x y = y

In einer strengen Sprache würden dann beide Zweige unabhängig vom Bedingungswert ausgewertet. Es wird schlimmer, wenn man Schleifen betrachtet. Alle strengen Lösungen erfordern, dass die Sprache Ihnen ein Zitat oder eine explizite Lambda-Konstruktion liefert.

In diesem Sinne können einige der besten Mechanismen für den Umgang mit Nebenwirkungen im Typensystem, wie z. B. Monaden, nur in einer faulen Umgebung effektiv zum Ausdruck gebracht werden. Dies lässt sich durch einen Vergleich der Komplexität der Workflows von F # mit den Haskell-Monaden belegen. (Sie können eine Monade in einer strengen Sprache definieren, aber leider scheitern Sie häufig an ein oder zwei Monadengesetzen, weil es Ihnen an Faulheit mangelt und Workflows im Vergleich dazu eine Menge strenges Gepäck aufnehmen.)

Edward KMETT
quelle
5
Sehr schön; Das sind die wirklichen Antworten. Früher dachte ich, es gehe um Effizienz (Verzögerung der Berechnungen für später), bis ich Haskell in erheblichem Umfang verwendete und sah, dass dies überhaupt nicht der Grund ist.
Owen
11
Auch wenn es technisch nicht stimmt, dass eine faule Sprache rein sein muss (R als Beispiel), ist es wahr, dass eine unreine faule Sprache sehr seltsame Dinge tun kann (R als Beispiel).
Owen
4
Sicher gibt es. In einer strengen Sprache ist rekursiv letein gefährliches Tier, im R6RS-Schema können zufällige Zeichen #fin Ihrem Begriff erscheinen, wo immer das Binden des Knotens streng zu einem Zyklus führte! Kein Wortspiel beabsichtigt, aber streng rekursivere letBindungen sind in einer faulen Sprache sinnvoll. Strenge verschärft auch die Tatsache, dass es whereüberhaupt keine Möglichkeit gibt, die relativen Effekte zu ordnen, außer bei SCC. Es handelt sich um eine Konstruktion auf Anweisungsebene. Die Auswirkungen können in beliebiger Reihenfolge auftreten, und selbst wenn Sie eine reine Sprache haben, werden Sie mit der #fProblem. Strenge whereRätsel Ihren Code mit nicht lokalen Bedenken.
Edward KMETT
2
Können Sie erklären, wie Faulheit hilft, die Werteinschränkung zu vermeiden? Ich habe das nicht verstehen können.
Tom Ellis
3
@PaulBone Worüber sprichst du? Faulheit hat viel mit Kontrollstrukturen zu tun. Wenn Sie Ihre eigene Kontrollstruktur in einer strengen Sprache definieren, müssen Sie entweder ein paar Lambdas oder ähnliches verwenden, oder es wird scheiße. Denn ifFunc(True, x, y)wird beides bewerten xund ynicht nur x.
Semikolon
28

Es gibt einen Unterschied zwischen einer normalen Auftragsbewertung und einer verzögerten Bewertung (wie in Haskell).

square x = x * x

Auswertung des folgenden Ausdrucks ...

square (square (square 2))

... mit eifriger Bewertung:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... mit normaler Auftragsbewertung:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... mit fauler Bewertung:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

Das liegt daran, dass die verzögerte Auswertung den Syntaxbaum betrachtet und Baumtransformationen durchführt ...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

... während bei der normalen Auftragsbewertung nur Texterweiterungen vorgenommen werden.

Aus diesem Grund werden wir bei der Verwendung der verzögerten Bewertung leistungsfähiger (die Bewertung endet häufiger als bei anderen Strategien), während die Leistung einer eifrigen Bewertung entspricht (zumindest in O-Notation).

Thomas Danecker
quelle
25

Lazy Evaluation in Bezug auf CPU genauso wie Garbage Collection in Bezug auf RAM. Mit GC können Sie so tun, als hätten Sie unbegrenzt Speicherplatz und fordern so viele Objekte im Speicher an, wie Sie benötigen. Die Laufzeit fordert automatisch unbrauchbare Objekte zurück. Mit LE können Sie so tun, als hätten Sie unbegrenzte Rechenressourcen - Sie können so viele Berechnungen durchführen, wie Sie benötigen. Die Laufzeit führt einfach keine unnötigen (für den gegebenen Fall) Berechnungen aus.

Was ist der praktische Vorteil dieser "vorgetäuschten" Modelle? Es befreit Entwickler (bis zu einem gewissen Grad) von der Verwaltung von Ressourcen und entfernt Boilerplate-Code aus Ihren Quellen. Wichtiger ist jedoch, dass Sie Ihre Lösung in einer größeren Anzahl von Kontexten effizient wiederverwenden können.

Stellen Sie sich vor, Sie haben eine Liste mit Zahlen S und eine Zahl N. Sie müssen aus Liste S die Nummer N finden, die der Zahl N am nächsten kommt. Sie können zwei Kontexte haben: einzelnes N und eine Liste L von Ns (ei für jedes N in L. Sie suchen das nächste M in S). Wenn Sie die verzögerte Auswertung verwenden, können Sie S sortieren und die binäre Suche anwenden, um das nächstgelegene M zu N zu finden. Für eine gute verzögerte Sortierung sind O-Schritte (Größe (S)) für einzelne N- und O-Schritte (ln (Größe (S)) * erforderlich. (Größe (S) + Größe (L))) Schritte für gleichmäßig verteiltes L. Wenn Sie keine verzögerte Bewertung haben, um die optimale Effizienz zu erzielen, müssen Sie einen Algorithmus für jeden Kontext implementieren.

Alexey
quelle
Die Analogie mit dem GC hat mir ein bisschen geholfen, aber können Sie bitte ein Beispiel für "Entfernt etwas Boilerplate-Code" geben?
Abdul
1
@Abdul, ein Beispiel, das jedem ORM-Benutzer bekannt ist: Lazy Association Loading. Es lädt die Zuordnung "just in time" aus der Datenbank und befreit gleichzeitig einen Entwickler von der Notwendigkeit, explizit anzugeben, wann sie geladen und wie sie zwischengespeichert werden sollen (dies ist das Boilerplate, das ich meine). Hier ist ein weiteres Beispiel: projectlombok.org/features/GetterLazy.html .
Alexey
25

Wenn Sie Simon Peyton Jones glauben, ist eine faule Bewertung per se nicht wichtig, sondern nur als „Haarhemd“, das die Designer dazu gezwungen hat, die Sprache rein zu halten. Ich finde mich mit diesem Standpunkt einverstanden.

Richard Bird, John Hughes und in geringerem Maße Ralf Hinze sind in der Lage, mit fauler Bewertung erstaunliche Dinge zu tun. Das Lesen ihrer Arbeit wird Ihnen helfen, sie zu schätzen. Zu guten Ausgangspunkten gehören Birds großartiger Sudoku- Löser und Hughes 'Artikel über Why Functional Programming Matters .

Norman Ramsey
quelle
Es zwang sie nicht nur , die Sprache rein zu halten, sondern erlaubte ihnen auch, dies zu tun, wenn (vor der Einführung der IOMonade) die Signatur von sein mainwürde String -> Stringund Sie bereits richtig interaktive Programme schreiben konnten.
links um den
@leftaroundabout: Was hindert eine strenge Sprache daran, alle Effekte in eine IOMonade zu zwingen ?
Tom Ellis
13

Betrachten Sie ein Tic-Tac-Toe-Programm. Dies hat vier Funktionen:

  • Eine Funktion zum Generieren von Zügen, die ein aktuelles Board verwendet und eine Liste neuer Boards mit jeweils einem Zug generiert.
  • Dann gibt es eine "Bewegungsbaum" -Funktion, die die Bewegungsgenerierungsfunktion anwendet, um alle möglichen Brettpositionen abzuleiten, die sich aus dieser ergeben könnten.
  • Es gibt eine Minimax-Funktion, die über den Baum (oder möglicherweise nur einen Teil davon) läuft, um den besten nächsten Schritt zu finden.
  • Es gibt eine Board-Evaluierungsfunktion, die feststellt, ob einer der Spieler gewonnen hat.

Dies schafft eine schöne klare Trennung der Bedenken. Insbesondere die Bewegungsgenerierungsfunktion und die Brettbewertungsfunktionen sind die einzigen, die die Spielregeln verstehen müssen: Die Bewegungsbaum- und Minimax-Funktionen sind vollständig wiederverwendbar.

Versuchen wir nun, Schach anstelle von Tic-Tac-Toe zu implementieren. In einer "eifrigen" (dh konventionellen) Sprache funktioniert dies nicht, da der Verschiebungsbaum nicht in den Speicher passt. Daher müssen jetzt die Board-Evaluierungs- und Bewegungsgenerierungsfunktionen mit dem Bewegungsbaum und der Minimax-Logik gemischt werden, da die Minimax-Logik verwendet werden muss, um zu entscheiden, welche Bewegungen generiert werden sollen. Unsere schöne saubere modulare Struktur verschwindet.

In einer faulen Sprache werden die Elemente des Verschiebungsbaums jedoch nur als Reaktion auf Anforderungen der Minimax-Funktion generiert: Der gesamte Verschiebungsbaum muss nicht generiert werden, bevor Minimax auf dem obersten Element losgelassen wird. Unsere saubere modulare Struktur funktioniert also immer noch in einem echten Spiel.

Paul Johnson
quelle
1
[In einer "eifrigen" (dh konventionellen) Sprache funktioniert dies nicht, da der Verschiebungsbaum nicht in den Speicher passt] - für Tic-Tac-Toe sicherlich. Es sind höchstens 3 ** 9 = 19683 Positionen zu speichern. Wenn wir jedes in extravaganten 50 Bytes speichern, ist das fast ein Megabyte. Das ist nichts ...
Jonas Kölker
6
Ja, das ist mein Punkt. Eifrige Sprachen können eine saubere Struktur für triviale Spiele haben, müssen diese Struktur jedoch für alles Reale kompromittieren. Faule Sprachen haben dieses Problem nicht.
Paul Johnson
3
Um fair zu sein, kann eine verzögerte Auswertung zu eigenen Speicherproblemen führen. Es ist nicht ungewöhnlich, dass Leute fragen, warum Haskell sein Gedächtnis für etwas ausbläst, das in einer eifrigen Bewertung einen Speicherverbrauch von O (1) haben würde
RHSeeger
@PaulJohnson Wenn Sie alle Positionen bewerten, spielt es keine Rolle, ob Sie sie eifrig oder faul bewerten. Die gleiche Arbeit muss getan werden. Wenn Sie in der Mitte anhalten und nur die Hälfte der Positionen bewerten, macht dies ebenfalls keinen Unterschied, da in beiden Fällen die Hälfte der Arbeit erledigt werden muss. Der einzige Unterschied zwischen den beiden Bewertungen besteht darin, dass der Algorithmus besser aussieht, wenn er träge geschrieben wird.
Ceving
12

Hier sind zwei weitere Punkte, von denen ich glaube, dass sie noch nicht in der Diskussion angesprochen wurden.

  1. Faulheit ist ein Synchronisationsmechanismus in einer gleichzeitigen Umgebung. Es ist eine einfache und einfache Möglichkeit, einen Verweis auf eine Berechnung zu erstellen und die Ergebnisse unter vielen Threads zu teilen. Wenn mehrere Threads versuchen, auf einen nicht bewerteten Wert zuzugreifen, wird er nur von einem ausgeführt, und die anderen blockieren ihn entsprechend und erhalten den Wert, sobald er verfügbar ist.

  2. Faulheit ist von grundlegender Bedeutung für die Amortisation von Datenstrukturen in einer reinen Umgebung. Dies wird von Okasaki in " Rein funktionale Datenstrukturen" ausführlich beschrieben. Die Grundidee ist jedoch, dass die verzögerte Auswertung eine kontrollierte Form der Mutation ist, die für die effiziente Implementierung bestimmter Arten von Datenstrukturen von entscheidender Bedeutung ist. Während wir oft von Faulheit sprechen, die uns zwingt, das reine Haarhemd zu tragen, gilt auch der andere Weg: Es handelt sich um ein Paar synergistischer Sprachmerkmale.

Edward Z. Yang
quelle
10

Wenn Sie Ihren Computer einschalten und Windows nicht jedes einzelne Verzeichnis auf Ihrer Festplatte im Windows Explorer öffnet und nicht jedes einzelne auf Ihrem Computer installierte Programm startet, bis Sie angeben, dass ein bestimmtes Verzeichnis oder ein bestimmtes Programm benötigt wird, ist dies der Fall ist "faul" Bewertung.

Die "faule" Auswertung führt Operationen aus, wann und wie sie benötigt werden. Dies ist nützlich, wenn es sich um eine Funktion einer Programmiersprache oder -bibliothek handelt, da es im Allgemeinen schwieriger ist, eine verzögerte Auswertung selbst zu implementieren, als einfach alles im Voraus vorab zu berechnen.

Yfeldblum
quelle
1
Einige Leute könnten sagen, dass das wirklich "faule Ausführung" ist. Der Unterschied ist wirklich unerheblich, außer in einigermaßen reinen Sprachen wie Haskell; Der Unterschied besteht jedoch darin, dass nicht nur die Berechnung verzögert wird, sondern auch die damit verbundenen Nebenwirkungen (wie das Öffnen und Lesen von Dateien).
Owen
8

Bedenken Sie:

if (conditionOne && conditionTwo) {
  doSomething();
}

Die Methode doSomething () wird nur ausgeführt, wenn conditionOne true und conditionTwo true ist. In dem Fall, in dem conditionOne falsch ist, warum müssen Sie das Ergebnis von conditionTwo berechnen? Die Bewertung von conditionTwo ist in diesem Fall Zeitverschwendung, insbesondere wenn Ihr Zustand das Ergebnis eines Methodenprozesses ist.

Das ist ein Beispiel für das faule Bewertungsinteresse ...

Romain Linsolas
quelle
Ich dachte, das wäre ein Kurzschluss, keine faule Bewertung.
Thomas Owens
2
Es ist eine verzögerte Auswertung, da conditionTwo nur berechnet wird, wenn es wirklich benötigt wird (dh wenn conditionOne wahr ist).
Romain Linsolas
7
Ich nehme an, Kurzschluss ist ein entarteter Fall von fauler Bewertung, aber es ist definitiv keine übliche Art, darüber nachzudenken.
Rmeador
19
Kurzschluss ist in der Tat ein Sonderfall der trägen Bewertung. Lazy Evaluation umfasst natürlich weit mehr als nur einen Kurzschluss. Oder was hat Kurzschluss über die träge Bewertung hinaus?
Yfeldblum
2
@ Julia: Du hast eine starke Definition von 'faul'. Ihr Beispiel für eine Funktion mit zwei Parametern ist nicht dasselbe wie eine if-Kurzschlussanweisung. Eine Kurzschluss-if-Anweisung vermeidet unnötige Berechnungen. Ich denke, ein besserer Vergleich zu Ihrem Beispiel wäre der Visual Basic-Operator "andalso", der die Auswertung beider Bedingungen
8
  1. Es kann die Effizienz steigern. Dies ist das offensichtlich aussehende, aber es ist nicht das wichtigste. (Beachten Sie auch, dass Faulheit auch die Effizienz beeinträchtigen kann - diese Tatsache ist nicht sofort offensichtlich. Wenn Sie jedoch viele temporäre Ergebnisse speichern, anstatt sie sofort zu berechnen, können Sie eine große Menge an RAM verbrauchen.)

  2. Sie können Flusssteuerungskonstrukte in normalem Code auf Benutzerebene definieren, anstatt sie in der Sprache fest zu codieren. (ZB hat Java forSchleifen; Haskell hat eine forFunktion. Java hat Ausnahmebehandlung; Haskell hat verschiedene Arten von Ausnahmemonaden. C # hat goto; Haskell hat die Fortsetzungsmonade ...)

  3. Sie können den Algorithmus zum Generieren von Daten vom Algorithmus entkoppeln, um zu entscheiden, wie viele Daten generiert werden sollen. Sie können eine Funktion schreiben, die eine fiktiv unendliche Liste von Ergebnissen generiert, und eine andere Funktion, die so viel von dieser Liste verarbeitet, wie sie benötigt. Genauer gesagt, Sie können fünf Generatorfunktionen und fünf Verbraucherfunktionen haben und jede Kombination effizient erstellen - anstatt manuell 5 x 5 = 25 Funktionen zu codieren, die beide Aktionen gleichzeitig kombinieren. (!) Wir alle wissen, dass Entkopplung eine gute Sache ist.

  4. Es zwingt Sie mehr oder weniger dazu, eine reine funktionale Sprache zu entwerfen . Es ist immer verlockend, Abkürzungen zu verwenden, aber in einer faulen Sprache macht die geringste Unreinheit Ihren Code wild unvorhersehbar, was stark gegen die Verwendung von Verknüpfungen spricht .

MathematicalOrchid
quelle
6

Ein großer Vorteil der Faulheit ist die Fähigkeit, unveränderliche Datenstrukturen mit angemessenen amortisierten Grenzen zu schreiben. Ein einfaches Beispiel ist ein unveränderlicher Stapel (mit F #):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

Der Code ist vernünftig, aber das Anhängen von zwei Stapeln x und y benötigt in den besten, schlechtesten und durchschnittlichen Fällen die Zeit O (Länge von x). Das Anhängen von zwei Stapeln ist eine monolithische Operation, die alle Knoten in Stapel x berührt.

Wir können die Datenstruktur als Lazy Stack neu schreiben:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazyfunktioniert, indem die Auswertung von Code in seinem Konstruktor angehalten wird. Nach der Auswertung mit .Force()wird der Rückgabewert zwischengespeichert und bei jeder weiteren Wiederverwendung wiederverwendet .Force().

In der Lazy-Version sind Anhänge eine O (1) -Operation: Sie geben 1 Knoten zurück und unterbrechen die eigentliche Neuerstellung der Liste. Wenn Sie den Kopf dieser Liste erhalten, wird der Inhalt des Knotens ausgewertet, wodurch er gezwungen wird, den Kopf zurückzugeben und eine Aufhängung mit den verbleibenden Elementen zu erstellen. Daher ist es eine O (1) -Operation, den Kopf der Liste zu übernehmen.

Unsere faule Liste wird also ständig neu erstellt. Sie zahlen die Kosten für die Neuerstellung dieser Liste erst, wenn Sie alle ihre Elemente durchlaufen haben. Mit Faulheit unterstützt diese Liste das O (1) -Konsumieren und Anhängen. Interessanterweise ist es durchaus möglich, eine Liste mit potenziell unendlichen Elementen zu erstellen, da wir Knoten erst nach ihrem Zugriff auswerten.

Die obige Datenstruktur erfordert nicht, dass Knoten bei jedem Durchlauf neu berechnet werden, sodass sie sich deutlich von Vanilla IEnumerables in .NET unterscheiden.

Julia
quelle
5

Dieses Snippet zeigt den Unterschied zwischen fauler und nicht fauler Bewertung. Natürlich könnte diese Fibonacci-Funktion selbst optimiert werden und eine verzögerte Auswertung anstelle einer Rekursion verwenden, aber das würde das Beispiel verderben.

Nehmen wir an , wir DÜRFEN die 20 ersten Zahlen für etwas zu verwenden haben, mit nicht faul Auswertung alle 20 Zahlen im Voraus erzeugt werden müssen, aber mit lazy evaluation werden sie erzeugt werden , wie nur benötigt. Somit zahlen Sie bei Bedarf nur den Berechnungspreis.

Beispielausgabe

Nicht faule Generation: 0.023373
Faule Generation: 0,000009
Nicht träge Ausgabe: 0,000921
Fauler Ausgang: 0.024205
import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)
Vinko Vrsalovic
quelle
5

Eine verzögerte Auswertung ist bei Datenstrukturen am nützlichsten. Sie können ein Array oder einen Vektor definieren, indem Sie nur bestimmte Punkte in der Struktur induktiv angeben und alle anderen in Bezug auf das gesamte Array ausdrücken. Auf diese Weise können Sie Datenstrukturen sehr präzise und mit hoher Laufzeitleistung generieren.

Um dies in Aktion zu sehen, können Sie sich meine Bibliothek für neuronale Netze mit dem Namen instinct ansehen . Die faule Bewertung für Eleganz und hohe Leistung wird stark genutzt. Zum Beispiel werde ich die traditionell zwingende Aktivierungsberechnung völlig los. Ein einfacher fauler Ausdruck macht alles für mich.

Dies wird zum Beispiel in der Aktivierungsfunktion und auch im Backpropagation-Lernalgorithmus verwendet (ich kann nur zwei Links posten, daher müssen Sie die learnPatFunktion im AI.Instinct.Train.DeltaModul selbst nachschlagen ). Traditionell erfordern beide viel kompliziertere iterative Algorithmen.

ertes
quelle
4

Andere Leute gaben bereits alle wichtigen Gründe an, aber ich denke, eine nützliche Übung, um zu verstehen, warum Faulheit wichtig ist, besteht darin, zu versuchen, eine Festkommafunktion in einer strengen Sprache zu schreiben .

In Haskell ist eine Festkommafunktion sehr einfach:

fix f = f (fix f)

dies erweitert sich auf

f (f (f ....

aber weil Haskell faul ist, ist diese unendliche Berechnungskette kein Problem; Die Auswertung erfolgt "von außen nach innen" und alles funktioniert wunderbar:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

Wichtig ist, dass es nicht darauf ankommt, fixfaul zu sein, sondern ffaul zu sein. Sobald Sie bereits eine strenge Richtlinie erhalten haben f, können Sie entweder Ihre Hände in die Luft werfen und aufgeben oder sie erweitern und sie durcheinander bringen. (Dies ist sehr ähnlich zu dem, was Noah darüber sagte, dass es sich um eine Bibliothek handelt , die streng / faul ist, nicht um die Sprache).

Stellen Sie sich nun vor, Sie schreiben dieselbe Funktion in der strengen Scala:

def fix[A](f: A => A): A = f(fix(f))

val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

Sie erhalten natürlich einen Stapelüberlauf. Wenn es funktionieren soll, müssen Sie das fArgument Call-by-Need ausführen:

def fix[A](f: (=>A) => A): A = f(fix(f))

def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)

val fact = fix(fact1)
Owen
quelle
3

Ich weiß nicht, wie Sie derzeit über Dinge denken, aber ich finde es nützlich, die verzögerte Bewertung eher als Bibliotheksproblem als als Sprachfunktion zu betrachten.

Ich meine, dass ich in strengen Sprachen eine verzögerte Auswertung implementieren kann, indem ich einige Datenstrukturen aufbaue, und in faulen Sprachen (zumindest Haskell) kann ich nach Strenge fragen, wenn ich es will. Daher macht die Sprachauswahl Ihre Programme nicht wirklich faul oder nicht faul, sondern wirkt sich einfach auf die aus, die Sie standardmäßig erhalten.

Wenn Sie sich das einmal so vorgestellt haben, denken Sie an alle Stellen, an denen Sie eine Datenstruktur schreiben, die Sie später zum Generieren von Daten verwenden können (ohne vorher zu viel darauf zu achten), und Sie werden viele Verwendungszwecke für Faulheit sehen Auswertung.

Noah Lavine
quelle
1
Die Implementierung einer verzögerten Bewertung in strengen Sprachen ist häufig eine Turing-Tarpit.
Itsbruce
2

Die nützlichste Ausnutzung der verzögerten Auswertung, die ich verwendet habe, war eine Funktion, die eine Reihe von Unterfunktionen in einer bestimmten Reihenfolge aufrief. Wenn eine dieser Unterfunktionen fehlschlug (false zurückgegeben), musste die aufrufende Funktion sofort zurückgegeben werden. Also hätte ich es so machen können:

bool Function(void) {
  if (!SubFunction1())
    return false;
  if (!SubFunction2())
    return false;
  if (!SubFunction3())
    return false;

(etc)

  return true;
}

oder die elegantere Lösung:

bool Function(void) {
  if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
    return false;
  return true;
}

Sobald Sie es verwenden, sehen Sie Möglichkeiten, es immer häufiger zu verwenden.

Marc Bernier
quelle
2

Ohne faule Bewertung dürfen Sie so etwas nicht schreiben:

  if( obj != null  &&  obj.Value == correctValue )
  {
    // do smth
  }
Peeles
quelle
Nun, imo, das ist eine schlechte Idee, das zu tun. Obwohl dieser Code möglicherweise korrekt ist (je nachdem, was Sie erreichen möchten), ist er schwer zu lesen, was immer eine schlechte Sache ist.
Brann
12
Das glaube ich nicht. Es ist eine Standardkonstruktion in C und seinen Verwandten.
Paul Johnson
Dies ist ein Beispiel für eine Kurzschlussbewertung, nicht für eine verzögerte Bewertung. Oder ist das effektiv dasselbe?
RufusVS
2

Faule Sprachen ermöglichen unter anderem mehrdimensionale unendliche Datenstrukturen.

Während Schema, Python usw. eindimensionale unendliche Datenstrukturen mit Streams zulassen, können Sie nur eine Dimension durchlaufen.

Faulheit ist nützlich für das gleiche Randproblem , aber es lohnt sich, die in diesem Link erwähnte Coroutinen-Verbindung zu beachten.

Shapr
quelle
2

Eine träge Bewertung ist das Gleichungsargument des armen Mannes (von dem im Idealfall erwartet werden kann, dass es die Eigenschaften des Codes aus den Eigenschaften der beteiligten Typen und Operationen ableitet).

Beispiel, wo es ganz gut funktioniert : sum . take 10 $ [1..10000000000]. Was uns nichts ausmacht, auf eine Summe von 10 Zahlen reduziert zu werden, anstatt nur auf eine direkte und einfache numerische Berechnung. Ohne die faule Auswertung würde dies natürlich eine gigantische Liste im Speicher erstellen, nur um die ersten 10 Elemente zu verwenden. Es wäre sicherlich sehr langsam und könnte einen Fehler aufgrund von Speichermangel verursachen.

Beispiel, wo es nicht so toll ist, wie wir möchten : sum . take 1000000 . drop 500 $ cycle [1..20]. Welches summiert tatsächlich die 1 000 000 Zahlen, selbst wenn in einer Schleife statt in einer Liste; Dennoch sollte es auf nur eine direkte numerische Berechnung mit wenigen Bedingungen und wenigen Formeln reduziert werden. Das wäre viel besser, als die 1 000 000 Zahlen zusammenzufassen. Auch wenn in einer Schleife und nicht in einer Liste (dh nach der Entwaldungsoptimierung).


Eine andere Sache ist, dass es möglich ist, im Modulo-Cons- Stil der Schwanzrekursion zu codieren , und es funktioniert einfach .

vgl. verwandte Antwort .

Will Ness
quelle
1

Wenn mit "fauler Auswertung" gemeint ist, wie in Combound-Booleschen, wie in

   if (ConditionA && ConditionB) ... 

Dann lautet die Antwort einfach: Je weniger CPU-Zyklen das Programm verbraucht, desto schneller wird es ausgeführt. Wenn ein Teil der Verarbeitungsanweisungen keinen Einfluss auf das Ergebnis des Programms hat, ist dies nicht erforderlich (und daher eine Verschwendung) von Zeit), um sie trotzdem durchzuführen ...

wenn otoh, meinst du das, was ich als "faule Initialisierer" bezeichnet habe, wie in:

class Employee
{
    private int supervisorId;
    private Employee supervisor;

    public Employee(int employeeId)
    {
        // code to call database and fetch employee record, and 
        //  populate all private data fields, EXCEPT supervisor
    }
    public Employee Supervisor
    { 
       get 
          { 
              return supervisor?? (supervisor = new Employee(supervisorId)); 
          } 
    }
}

Diese Technik ermöglicht es dem Client-Code, die Klasse zu verwenden, um zu vermeiden, dass die Datenbank für den Supervisor-Datensatz aufgerufen werden muss, es sei denn, der Client, der das Employee-Objekt verwendet, benötigt Zugriff auf die Supervisor-Daten. Dies beschleunigt die Instanziierung eines Mitarbeiters. Wenn Sie jedoch den Supervisor benötigen, löst der erste Aufruf der Supervisor-Eigenschaft den Datenbankaufruf aus und die Daten werden abgerufen und sind verfügbar ...

Charles Bretana
quelle
0

Auszug aus Funktionen höherer Ordnung

Lassen Sie uns die größte Zahl unter 100.000 finden, die durch 3829 teilbar ist. Dazu filtern wir nur eine Reihe von Möglichkeiten, in denen wir wissen, dass die Lösung liegt.

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0 

Wir machen zuerst eine Liste aller Zahlen unter 100.000, absteigend. Dann filtern wir es nach unserem Prädikat und da die Zahlen absteigend sortiert sind, ist die größte Zahl, die unser Prädikat erfüllt, das erste Element der gefilterten Liste. Wir mussten nicht einmal eine endliche Liste für unseren Startsatz verwenden. Das ist wieder Faulheit in Aktion. Da wir nur den Kopf der gefilterten Liste verwenden, spielt es keine Rolle, ob die gefilterte Liste endlich oder unendlich ist. Die Auswertung stoppt, wenn die erste geeignete Lösung gefunden wurde.

onmyway133
quelle