Structures de données en programmation fonctionnelle

Je joue actuellement avec LISP (en particulier Scheme et Clojure) et je me demande comment les structures de données typiques sont traitées dans les langages de programmation fonctionnels.

Par exemple, disons que je voudrais résoudre un problème en utilisant un algorithme de recherche de chemin de graphe. Comment pourrait-on généralement représenter ce graphique dans un langage de programmation fonctionnel (principalement intéressé par le style fonctionnel pur qui peut être appliqué à LISP)? Aurais-je simplement oublié les graphiques et résolu le problème d'une autre manière?

Cela fait un moment que je n'ai pas travaillé dans LISP, mais si je me souviens bien, la structure non atomique de base est une liste. Tout le reste est basé sur cela. Vous pourriez donc avoir une liste d'atomes où chaque atome est un nœud suivi d'une liste de bords qui connectent le nœud à d'autres nœuds. Je suis sûr qu'il y a aussi d'autres façons de le faire.

Peut-être quelque chose comme ça:

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

pourrait donner un graphique comme celui-ci:

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

Si vous voulez devenir chic, vous pouvez également lui ajouter des poids:

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

Vous pourriez également être intéressé par ceci: CL-Graph (trouvé en recherchant sur Google l'expression "structure graphique lisp")

Les langages fonctionnels traitent les structures de données de la même manière que les langages non fonctionnels: en séparant l'interface de l'implémentation, en créant des types de données abstraits.

Vous pouvez créer des types de données abstraits dans Lisp. Par exemple, pour un graphique, vous voudrez peut-être quelques fonctions:

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

Une fois que vous avez créé cette interface dans un graphique, vous pouvez implémenter les structures de données réelles de différentes manières, en optimisant éventuellement des facteurs tels que l'efficacité du programmeur, la flexibilité et l'efficacité de calcul.

La clé est de s'assurer que le code qui utilise des graphiques utilise uniquement l'interface graphique et n'accède pas à l'implémentation sous-jacente. Cela gardera le code client plus simple car il est dissocié de l'implémentation réelle.

Eh bien, cela dépendra si votre graphique est orienté / non orienté, pondéré / non pondéré, mais une façon de représenter un graphique orienté et pondéré (qui serait le plus général) consiste à utiliser une carte de cartes (dans Clojure)

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

représenterait une carte avec des nœuds: a: b et: c. : a pointe vers: b avec un poids de 3 et: c avec un poids de 4.: b pointe vers: a avec un poids de 1.: c ne pointe vers rien.

En Common Lisp, si j'avais besoin de représenter un arbre, j'utiliserais soit une liste (si c'était juste pour un hack rapide), soit je définirais une classe d'arbre (ou struct, mais les classes interagissent bien avec les fonctions génériques, alors pourquoi pas) .

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

Si j'ai besoin d'arbres littéraux dans le code, je définirais probablement aussi une make-treefonction qui prend une représentation de liste de l'arbre que je veux et le transforme en arbre d'arbres-objets.

Dans Haskell, la liste est la structure de données de base et si vous voulez des structures de données plus avancées, vous utilisez souvent des structures récursives comme un arbre est nul ou un nœud et deux arbres

data Tree a = Null | Node Tree a Tree