Strutture dati nella programmazione funzionale

È passato un po 'di tempo da quando ho lavorato in LISP, ma, come ricordo, la struttura non atomica di base è una lista. Tutto il resto si basa su questo. Quindi potresti avere un elenco di atomi in cui ogni atomo è un nodo seguito da un elenco di spigoli che collegano il nodo ad altri nodi. Sono sicuro che ci sono anche altri modi per farlo.

Forse qualcosa del genere:

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

potrebbe dare un grafico come questo:

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

Se vuoi divertirti, puoi aggiungere anche dei pesi:

(
  (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))
)

Potresti anche essere interessato a questo: CL-Graph (trovato da google-cercando la frase " lisp graph structure ")

I linguaggi funzionali si occupano delle strutture dati nello stesso modo dei linguaggi non funzionali: separando l'interfaccia dall'implementazione, creando tipi di dati astratti.

È possibile creare tipi di dati astratti in Lisp. Ad esempio, per un grafico, potresti volere un paio di funzioni:

(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
  ...)

Una volta creata questa interfaccia su un grafico, è possibile implementare le strutture dati effettive in molti modi diversi, possibilmente ottimizzando fattori quali l'efficienza del programmatore, la flessibilità e l'efficienza computazionale.

La chiave è assicurarsi che il codice che utilizza i grafici solo utilizzi l'interfaccia del grafico e non acceda all'implementazione sottostante. Ciò manterrà il codice client più semplice in quanto separato dall'attuale implementazione.

Bene dipenderà dal fatto che il tuo grafico sia diretto / non orientato, ponderato / non ponderato, ma un modo per rappresentare un grafico ponderato diretto (che sarebbe il più generale) è con una mappa di mappe (in Clojure)

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

rappresenterebbe una mappa con i nodi: a: b e: c. : a punta a: b con un peso di 3 e: c con un peso di 4.: b punta a: a con un peso di 1.: c non punta a nulla.

In Common Lisp, se avessi bisogno di rappresentare un albero, userei una lista (se fosse solo per un attacco rapido) o definire una classe tree (o struct, ma le classi interagiscono bene con le funzioni generiche, quindi perché no?

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

Se ho bisogno di alberi letterali nel codice, probabilmente definirò anche una funzione make-tree che prende una rappresentazione di lista dell'albero che voglio e lo trasforma in un albero di oggetti-albero.

In Haskell la lista è la struttura di base dei dati e se vuoi una trama di dati più avanzata usi spesso strukture ricorsive come un albero è nullo o un nodo e due alberi

data Tree a = Null | Node Tree a Tree