Datenstrukturen in der funktionalen Programmierung

11

Ich spiele derzeit mit LISP (insbesondere Scheme und Clojure) und frage mich, wie typische Datenstrukturen in funktionalen Programmiersprachen behandelt werden.

Angenommen, ich möchte ein Problem mithilfe eines Algorithmus zur Pfadfindung für Diagramme lösen. Wie würde man diesen Graphen normalerweise in einer funktionalen Programmiersprache darstellen (hauptsächlich interessiert an einem reinen funktionalen Stil, der auf LISP angewendet werden kann)? Würde ich die Grafiken einfach ganz vergessen und das Problem auf andere Weise lösen?

pwny
quelle

Antworten:

14

Es ist schon eine Weile her, dass ich in LISP gearbeitet habe, aber wie ich mich erinnere, ist die grundlegende nichtatomare Struktur eine Liste. Alles andere basiert darauf. Sie könnten also eine Liste von Atomen haben, wobei jedes Atom ein Knoten ist, gefolgt von einer Liste von Kanten, die den Knoten mit anderen Knoten verbinden. Ich bin mir sicher, dass es auch andere Möglichkeiten gibt.

Vielleicht so etwas:

(
  (a (b c)),
  (b (a c)),
  (c (a b d)),
  (d (c))
)

könnte eine Grafik wie diese geben:

a <--> b <--> c <--> d
^^
| |
+ --------- +

Wenn Sie Lust haben, können Sie auch Gewichte hinzufügen:

(
  (a (b 1.0 c 2.0)),
  (b (a 1.0 c 1.0)),
  (c (a 1.3 b 7.2 d 10.5)),
  (d (c -10.5))
)

Das könnte Sie auch interessieren: CL-Graph (gefunden durch Google-Suche nach dem Ausdruck "Lisp-Graph-Struktur")

FrustratedWithFormsDesigner
quelle
4
Dies ist etwas spät, aber ich denke, ich sollte warnen, dass "Alles andere basiert auf [Liste]" irreführend ist. Common Lisp, Scheme und Clojure haben alle Vektoren, Karten, Zeichenfolgen sowie Strukturen / Klassen, die nicht auf Listen aufgebaut sind. Der Code, den wir schreiben, um sie zu erstellen, ist im Allgemeinen eine Liste, z. B. (make-array '(2 2): Anfangselement 0), aber die Datenstruktur wird nicht mithilfe von Listen implementiert.
Coredump
3

Funktionale Sprachen behandeln Datenstrukturen genauso wie nicht funktionale Sprachen: indem sie die Schnittstelle von der Implementierung trennen und abstrakte Datentypen erstellen.

Sie können abstrakte Datentypen in Lisp erstellen. Für ein Diagramm möchten Sie möglicherweise einige Funktionen:

(define (get-vertices graph) ;; gets all the vertices from a graph
  ...)

(define (get-edges graph) ;; gets all the edges from a graph
  ...)

(define (get-weight vertex-from vertex-to) ;; get the weight of a specific vertex
  ...)

Sobald Sie diese Schnittstelle zu einem Diagramm erstellt haben, können Sie die tatsächlichen Datenstrukturen auf viele verschiedene Arten implementieren und möglicherweise Faktoren wie Programmierereffizienz, Flexibilität und Recheneffizienz optimieren.

Der Schlüssel besteht darin, sicherzustellen, dass der Code, der Diagramme verwendet, nur die Diagrammschnittstelle verwendet und nicht auf die zugrunde liegende Implementierung zugreift. Dadurch wird der Client-Code einfacher, da er von der tatsächlichen Implementierung entkoppelt ist.


quelle
2

Nun, es würde davon abhängen, ob Ihr Diagramm gerichtet / ungerichtet, gewichtet / ungewichtet ist, aber eine Möglichkeit, ein gerichtetes, gewichtetes Diagramm darzustellen (was am allgemeinsten wäre), ist eine Karte mit Karten (in Clojure).

{
 :a {:b 3 :c 4} 
 :b {:a 1} 
 :c {}
}

würde eine Karte mit Knoten darstellen: a: b und: c. : a zeigt auf: b mit einem Gewicht von 3 und: c mit einem Gewicht von 4 .: b zeigt auf: a mit einem Gewicht von 1 .: c zeigt auf nichts.

WuHoUnited
quelle
1

Wenn ich in Common Lisp einen Baum darstellen müsste, würde ich entweder eine Liste verwenden (wenn es nur für einen schnellen Hack wäre) oder eine Baumklasse definieren (oder eine Struktur, aber Klassen interagieren gut mit generischen Funktionen, warum also nicht)? .

(defclass tree ()
  ((node :accessor node :initarg :node)
   (children :accessor children :initarg :children)))

Wenn ich Literalbäume im Code benötige, würde ich wahrscheinlich auch eine make-treeFunktion definieren , die eine Listendarstellung des gewünschten Baums verwendet und ihn in einen Baum von Baumobjekten verwandelt.

Vatine
quelle
-2

In Haskell ist die Liste die grundlegende Datenstruktur. Wenn Sie erweiterte Datenstrukturen wünschen, verwenden Sie häufig rekursive Strukturen, z. B. ist ein Baum entweder null oder ein Knoten und zwei Bäume

data Tree a = Null | Node Tree a Tree  
nist
quelle