Was ist der Vorteil der rein funktionalen Datenstruktur?

Question

Es gibt eine große Anzahl von Texten auf Datenstrukturen und Bibliotheken von Datenstrukturen Code. Ich verstehe, dass rein funktionale Datenstruktur ist einfacher zu Grunde über. Jedoch habe ich Schwierigkeiten haben, die reale Welt Vorteil der Verwendung von rein funktionalen Datenstruktur in pragmatische Code (mit funktionalen Programmiersprache oder nicht) über den Imperativ Gegenstück zu verstehen. Kann jemand einige reale Welt Fall vor, rein funktionale Datenstruktur Vorteil hat, und warum?

Beispiele entlang der Linie, wie ich verwenden data_structure_name in programming_language tun Anwendung , weil es tun können certain_thing .

Danke.

PS: Was ich damit meine rein funktionale Datenstruktur nicht die gleichen wie persistente Datenstruktur ist. Persistente Datenstruktur ist eine Datenstruktur, die sich nicht ändert ?? Auf der anderen Seite rein funktionale Datenstruktur ist eine Datenstruktur, die rein tätig ist.

Answer 1

Rein funktionale (auch bekannt als persistent oder unveränderlich) Datenstrukturen geben Ihnen mehrere Vorteile:

• Sie nie, sie zu sperren haben, die extrem verbessert Gleichzeitigkeit .
• können sie Struktur teilen, die verringert den Speicherbedarf . Betrachten wir zum Beispiel Liste [1, 2, 3, 4] in Haskell und einige imperative Sprache wie Java. Zur Herstellung von neuer Liste in Haskell haben Sie nur neuen cons (Paar Werte und Referenz-to-next-Element) erstellen und verbinden Sie es mit der vorherige Liste. In Java müssen Sie völlig neue Liste erstellen nicht die vorherigen zu beschädigen.
• Sie können persistente Datenstrukturen faul .
• auch, wenn Sie funktionalen Stil verwenden, können Sie vermeiden Denken der Zeit und die Folge von Operationen , und so, Ihre Programme machen deklarative .
• Tatsache, dass die Datenstruktur unveränderlich ist, können Sie einige weitere Annahmen treffen und so erweitern Fähigkeiten der Sprache . Zum Beispiel Clojure nutzt die Tatsache der Unveränderlichkeit korrekt Implementierungen von HashCode bereitzustellen () für jedes Objekt, so dass jeder Gegenstand kann wird als Schlüssel in einer Karte verwendet.
• mit unveränderlichen Daten und funktionalen Stil Sie auch frei verwenden können memoization .

Es gibt viel mehr Vorteile, im Allgemeinen, es ist eine andere Art und Weise, die reale Welt zu modellieren. Diese und einige andere Kapitel aus SICP geben Ihnen eine genauere Ansicht mit unveränderlichen Strukturen zu programmieren, ihre Vor- und Nachteile.

Answer 2

Neben Shared-Memory-Sicherheit am reinsten Funktion Datenstrukturen geben Sie auch Ausdauer und praktisch kostenlos. Zum Beispiel, sagen wir mal ich einen set in OCaml haben, und ich möchte einige neue Werte, um es hinzuzufügen kann ich dies tun:

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

a Reste unmodifizierten , nachdem die neuen Zeichen hinzugefügt (es enthält nur ad), während b enthält ah, und sie teilen einige der gleichen Speicher (mit einem set es ist ein bisschen schwierig zu sagen, wie viel Speicher gemeinsam genutzt werden, da es ein AVL-Baum und die Form der Baumänderungen) sind. Ich kann dies auch weiterhin tun, alle Änderungen zu verfolgen ich auf den Baum gemacht habe mir erlaubt, in einen früheren Zustand zurück zu gehen.

Ist hier ein großes Diagramm aus dem Wikipedia-Artikel über rein funktionale dass zeigt die Ergebnisse des Einsatzes der Zeichen 'e' in den binären Baum xs:

Answer 3

Erlang-Programme verwenden rein funktionale Datenstrukturen fast ausschließlich, und sie ernten erhebliche Vorteile durch fast nahtlos an mehrere Kerne skalieren. Da die Daten gemeinsam genutzt (hauptsächlich Binärdateien und Bitketten) wird nicht verändert, es ist nie eine Notwendigkeit, solche Daten zu sperren.

Answer 4

Nehmen Sie diese kleine Schnipsel von F #:

let numbers = [1; 2; 3; 4; 5]

Sie können mit 100% iger Sicherheit sagen, dass das ist eine unveränderliche Liste der ganzen Zahlen 1 bis 5. Sie können auf diese Liste einen Verweis übergeben herum und haben nie zu befürchten, dass die Liste geändert wurde. Das ist Grund genug für mich, es zu benutzen.

Answer 5

rein funktionale Datenstrukturen haben die folgenden Vorteile:

• Persistence. Alte Versionen sicher in dem Wissen wiederverwendet werden können, dass sie nicht verändert wurden

• Sharing:. Viele Versionen einer Datenstruktur kann gleichzeitig mit nur geringen Speicheranforderungen gehalten werden

• Thema Sicherheit:. Jede Mutation innerhalb der faulen Thunks versteckt (falls vorhanden) und daher von der Sprachimplementierung behandelt

• Einfachheit. Nicht mit Spur von Zustandsänderungen zu halten macht rein funktionale Datenstrukturen einfacher zu bedienen, vor allem im Zusammenhang mit der Gleichzeitigkeit

• Inkrementalität. Rein funktionale Datenstrukturen aus vielen kleinen Teilen zusammengesetzt, wodurch sie ideal für inkrementelle Garbage Collection machen führende Latenzen zu senken

Beachten Sie, dass ich nicht Parallelität als Vorteil der rein funktionalen Datenstrukturen aufgelistet sind, weil ich glaube nicht, dass dies der Fall zu sein. Effiziente Multi-Core-Parallelität erfordert vorhersehbar Ort zu nutzen, um Caches und vermeiden auf dem gemeinsamen Zugriff auf dem Hauptspeicher Engpass zu werden und rein funktionale Datenstrukturen haben, im besten Fall, unbekannte Eigenschaften in dieser Hinsicht. Folglich viele Programme, die rein funktionale Datenstrukturen verwenden Sie auch nicht skaliert, wenn auf einem Multicore parallelisiert, weil sie alle ihre Zeit in Cache-Misses verbringen, streit für Shared-Memory-Wege.

Was ich damit meine rein funktionale Datenstruktur nicht das gleiche wie persistente Datenstruktur ist.

Es gibt einige Verwirrung hier. Im Rahmen der rein funktionaler Datenstrukturen, ist Persistenz ein Begriff verwendet, um die Fähigkeit zu beziehen sich auf frühere Versionen einer Datenstruktur in dem sicheren Wissen zu verweisen, dass sie noch gültig sind. Dies ist eine natürliche Folge der rein funktional zu sein, und daher Persistenz ist ein inhärentes Merkmal aller rein funktionalen Datenstrukturen.