[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki19\/2021\/01\/26\/rein-funktionale-datenstruktur-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki19\/2021\/01\/26\/rein-funktionale-datenstruktur-wikipedia\/","headline":"Rein funktionale Datenstruktur – Wikipedia","name":"Rein funktionale Datenstruktur – Wikipedia","description":"before-content-x4 In der Informatik a rein funktionale Datenstruktur ist eine Datenstruktur, die in einer rein funktionalen Sprache implementiert werden kann.","datePublished":"2021-01-26","dateModified":"2021-01-26","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki19\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki19\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":100,"height":100},"url":"https:\/\/wiki.edu.vn\/wiki19\/2021\/01\/26\/rein-funktionale-datenstruktur-wikipedia\/","wordCount":2159,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In der Informatik a rein funktionale Datenstruktur ist eine Datenstruktur, die in einer rein funktionalen Sprache implementiert werden kann.  Der Hauptunterschied zwischen einer beliebigen und einer rein funktionalen Datenstruktur besteht darin, dass letztere (stark) unver\u00e4nderlich ist.  Diese Einschr\u00e4nkung stellt sicher, dass die Datenstruktur die Vorteile unver\u00e4nderlicher Objekte besitzt: (vollst\u00e4ndige) Persistenz, schnelles Kopieren von Objekten und Thread-Sicherheit.  Effiziente rein funktionale Datenstrukturen erfordern m\u00f6glicherweise die Verwendung einer verz\u00f6gerten Auswertung und Speicherung.  Table of ContentsDefinition[edit]Sicherstellen, dass eine Datenstruktur rein funktionsf\u00e4hig ist[edit]Rein funktionale Datenstrukturen verwenden[edit]Beispiele[edit]Design und Implementierung[edit]Faulheit und Auswendiglernen[edit]Amortisierte Analyse und Planung[edit]Beispiel: Warteschlange[edit]Siehe auch[edit]Verweise[edit]Externe Links[edit]Definition[edit]Persistente Datenstrukturen haben die Eigenschaft, fr\u00fchere Versionen von sich selbst unver\u00e4ndert zu lassen.  Andererseits lassen Strukturen wie Arrays zu destruktives Update,[1]  Das hei\u00dft, ein Update, das nicht abgebrochen werden kann.  Sobald ein Programm einen Wert in einen Index des Arrays schreibt, kann sein vorhergehender Wert nicht mehr abgerufen werden.[citation needed]Formal a Rein funktionale Datenstruktur ist eine Datenstruktur, die in einer rein funktionalen Sprache wie Haskell implementiert werden kann.  In der Praxis bedeutet dies, dass die Datenstrukturen nur mit persistenten Datenstrukturen wie Tupeln, Summentypen, Produkttypen und Basistypen wie Ganzzahlen, Zeichen und Zeichenfolgen erstellt werden m\u00fcssen.  Eine solche Datenstruktur ist notwendigerweise persistent.  Alle persistenten Datenstrukturen sind jedoch nicht rein funktional.[1]::16  Beispielsweise ist ein best\u00e4ndiges Array eine Datenstruktur, die best\u00e4ndig ist und die unter Verwendung eines Arrays implementiert wird und daher nicht rein funktional ist.[citation needed]  Im Buch Rein funktionale Datenstrukturen, Okasaki vergleicht zerst\u00f6rerische Aktualisierungen mit den Messern des Meisterkochs.[1]::2  Destruktive Aktualisierungen k\u00f6nnen nicht r\u00fcckg\u00e4ngig gemacht werden und sollten daher nicht verwendet werden, es sei denn, es ist sicher, dass der vorherige Wert nicht mehr ben\u00f6tigt wird.  Destruktive Aktualisierungen k\u00f6nnen jedoch auch eine Effizienz erm\u00f6glichen, die mit anderen Techniken nicht erreicht werden kann.  Beispielsweise kann eine Datenstruktur, die ein Array und destruktive Aktualisierungen verwendet, durch eine \u00e4hnliche Datenstruktur ersetzt werden, wobei das Array durch eine Karte, eine Direktzugriffsliste oder einen ausgeglichenen Baum ersetzt wird, der eine rein funktionale Implementierung zul\u00e4sst.  Die Zugriffskosten k\u00f6nnen sich jedoch von konstanter Zeit zu logarithmischer Zeit erh\u00f6hen.[citation needed]Sicherstellen, dass eine Datenstruktur rein funktionsf\u00e4hig ist[edit]Eine Datenstruktur ist niemals von Natur aus funktionsf\u00e4hig.  Beispielsweise kann ein Stapel als einfach verkn\u00fcpfte Liste implementiert werden.  Diese Implementierung ist rein funktional, solange die einzigen Operationen auf dem Stapel einen neuen Stapel zur\u00fcckgeben, ohne den alten Stapel zu \u00e4ndern.  Wenn die Sprache jedoch nicht rein funktionsf\u00e4hig ist, kann das Laufzeitsystem m\u00f6glicherweise keine Unver\u00e4nderlichkeit garantieren.  Dies wird von Okasaki illustriert,[1]::9-11  wo er die Verkettung von zwei einfach verkn\u00fcpften Listen zeigt, kann immer noch mit einer imperativen Einstellung erfolgen.[citation needed]Um sicherzustellen, dass eine Datenstruktur in einer unreinen Funktionssprache rein funktional verwendet wird, k\u00f6nnen Module oder Klassen verwendet werden, um die Manipulation nur \u00fcber autorisierte Funktionen sicherzustellen.[citation needed]Rein funktionale Datenstrukturen verwenden[edit]Eine der zentralen Herausforderungen bei der Anpassung des vorhandenen Codes an rein funktionale Datenstrukturen besteht darin, dass ver\u00e4nderbare Datenstrukturen “versteckte Ausgaben” f\u00fcr Funktionen bereitstellen, die sie verwenden.  Um diese Funktionen umzuschreiben, um rein funktionale Datenstrukturen zu verwenden, m\u00fcssen diese Datenstrukturen als explizite Ausgaben hinzugef\u00fcgt werden.  Stellen Sie sich beispielsweise eine Funktion vor, die eine ver\u00e4nderbare Liste akzeptiert, ein Element in die Liste einf\u00fcgt und die L\u00e4nge der neuen Liste zur\u00fcckgibt.  In einer rein funktionalen Einstellung wird durch Einf\u00fcgen eines neuen Elements in die Liste eine neue Liste erstellt, die urspr\u00fcngliche jedoch nicht aktualisiert.  Um n\u00fctzlich zu sein, muss eine rein funktionale Version dieser Funktion wahrscheinlich sowohl die L\u00e4nge der Liste als auch die neue Liste selbst zur\u00fcckgeben.  Im allgemeinsten Fall muss ein auf diese Weise konvertiertes Programm den “Status” oder “Speicher” des Programms als zus\u00e4tzliches Ergebnis aus jedem Funktionsaufruf zur\u00fcckgeben.  Ein solches Programm soll im Store-Passing-Stil geschrieben sein.Beispiele[edit]Hier ist eine Liste abstrakter Datenstrukturen mit rein funktionalen Implementierungen:Stapel (first in, last out) als einfach verkn\u00fcpfte Liste implementiert,Warteschlange, implementiert als Echtzeitwarteschlange,Double-Ended-Warteschlange, implementiert als Double-Ended-Warteschlange in Echtzeit,(Multi) Satz geordneter Elemente und Karte, indiziert durch geordnete Schl\u00fcssel, implementiert als rot-schwarzer Baum oder allgemeiner durch einen Suchbaum.Priorit\u00e4tswarteschlange, implementiert als Brodal-WarteschlangeRandom Access List, implementiert als skew-bin\u00e4re Random Access ListHash consingRei\u00dfverschluss (Datenstruktur)Design und Implementierung[edit]In seinem Buch Rein funktionale DatenstrukturenDer Informatiker Chris Okasaki beschreibt Techniken zum Entwerfen und Implementieren rein funktionaler Datenstrukturen, von denen eine kleine Teilmenge im Folgenden zusammengefasst ist.Faulheit und Auswendiglernen[edit]Lazy Evaluation ist besonders interessant in einer rein funktionalen Sprache[1]::31  weil die Reihenfolge der Auswertung niemals das Ergebnis einer Funktion \u00e4ndert.  Eine verz\u00f6gerte Auswertung wird daher nat\u00fcrlich zu einem wichtigen Bestandteil beim Aufbau rein funktionaler Datenstrukturen.  Berechnungen k\u00f6nnen nur durchgef\u00fchrt werden, wenn das Ergebnis tats\u00e4chlich erforderlich ist.  Daher kann der Code einer rein funktionalen Datenstruktur ohne Effizienzverlust \u00e4hnliche Daten ber\u00fccksichtigen, die effektiv verwendet werden, und Daten, die ignoriert werden.  Die einzige Berechnung, die erforderlich ist, bezieht sich auf die erste Art von Daten, die tats\u00e4chlich ausgef\u00fchrt werden.[citation needed]Eines der wichtigsten Werkzeuge beim Aufbau effizienter, rein funktionaler Datenstrukturen ist das Auswendiglernen.[1]::31  Wenn eine Berechnung durchgef\u00fchrt wurde, wird sie gespeichert und muss nicht ein zweites Mal durchgef\u00fchrt werden.  Dies ist besonders wichtig bei verz\u00f6gerten Implementierungen.  Zus\u00e4tzliche Bewertungen erfordern m\u00f6glicherweise das gleiche Ergebnis, es ist jedoch unm\u00f6glich zu wissen, f\u00fcr welche Bewertung dies zuerst erforderlich ist.[citation needed]Amortisierte Analyse und Planung[edit]Einige Datenstrukturen, auch solche, die nicht rein funktional sind, wie z. B. dynamische Arrays, lassen einen Betrieb zu, der die meiste Zeit effizient (dh konstante Zeit f\u00fcr dynamische Arrays) und selten ineffizient (dh lineare Zeit f\u00fcr dynamische Arrays) ist. Amortisation kann dann verwendet werden, um zu beweisen, dass die durchschnittliche Laufzeit der Operationen effizient ist.[1]::39  Das hei\u00dft, die wenigen ineffizienten Operationen sind selten genug und \u00e4ndern nicht die asymptotische Entwicklung der Zeitkomplexit\u00e4t, wenn eine Folge von Operationen betrachtet wird.[citation needed]Im Allgemeinen ist es f\u00fcr persistente Datenstrukturen nicht akzeptabel, ineffiziente Operationen durchzuf\u00fchren, da genau diese Operation viele Male aufgerufen werden kann.  Dies ist weder f\u00fcr Echtzeit- noch f\u00fcr imperative Systeme akzeptabel, bei denen der Benutzer m\u00f6glicherweise ben\u00f6tigt, dass die von der Operation ben\u00f6tigte Zeit vorhersehbar ist.  Dar\u00fcber hinaus erschwert diese Unvorhersehbarkeit die Verwendung von Parallelit\u00e4t.[1]::83[citation needed]Um diese Probleme zu vermeiden, k\u00f6nnen Sie bei einigen Datenstrukturen den ineffizienten Betrieb verschieben – dies wird als Zeitplanung bezeichnet.[1]::84  Die einzige Voraussetzung ist, dass die Berechnung der ineffizienten Operation endet, bevor das Ergebnis tats\u00e4chlich ben\u00f6tigt wird.  Ein konstanter Teil der ineffizienten Operation wird gleichzeitig mit dem folgenden Aufruf einer effizienten Operation ausgef\u00fchrt, so dass die ineffiziente Operation bereits vollst\u00e4ndig ausgef\u00fchrt wird, wenn sie ben\u00f6tigt wird, und jede einzelne Operation effizient bleibt.[clarification needed]Beispiel: Warteschlange[edit]Amortisierte Warteschlangen[1]::65[1]::73  bestehen aus zwei einzeln verkn\u00fcpften Listen: der vorderen und der umgekehrten R\u00fcckseite.  Elemente werden der hinteren Liste hinzugef\u00fcgt und aus der vorderen Liste entfernt.  Wenn die vordere Warteschlange leer ist, wird die hintere Warteschlange umgekehrt und wird zur vorderen, w\u00e4hrend die hintere Warteschlange leer wird.  Die amortisierte Zeitkomplexit\u00e4t jeder Operation ist konstant.  Jede Zelle der Liste wird h\u00f6chstens einmal hinzugef\u00fcgt, umgekehrt und entfernt.  Um einen ineffizienten Vorgang zu vermeiden, bei dem die hintere Liste umgekehrt wird, f\u00fcgen Echtzeitwarteschlangen die Einschr\u00e4nkung hinzu, dass die hintere Liste nur so lang ist wie die vordere Liste.  Um sicherzustellen, dass die hintere Liste l\u00e4nger als die vordere Liste wird, wird die vordere Liste an die hintere Liste angeh\u00e4ngt und umgekehrt.  Da dieser Vorgang ineffizient ist, wird er nicht sofort ausgef\u00fchrt.  Stattdessen wird es f\u00fcr jede der Operationen ausgef\u00fchrt.  Somit wird jede Zelle berechnet, bevor sie ben\u00f6tigt wird, und die neue Frontliste wird vollst\u00e4ndig berechnet, bevor eine neue ineffiziente Operation aufgerufen werden muss.[citation needed]Siehe auch[edit]Verweise[edit]Externe Links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki19\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki19\/2021\/01\/26\/rein-funktionale-datenstruktur-wikipedia\/#breadcrumbitem","name":"Rein funktionale Datenstruktur – Wikipedia"}}]}]