Struktury danych w programowaniu funkcjonalnym

Obecnie gram w LISP (szczególnie Scheme i Clojure) i zastanawiam się, jak radzą sobie typowe struktury danych w funkcjonalnych językach programowania.

Na przykład, powiedzmy, że chciałbym rozwiązać problem za pomocą algorytmu znajdowania ścieżki wykresu. Jak można zazwyczaj przedstawiać ten wykres w funkcjonalnym języku programowania (przede wszystkim zainteresowany czystym stylem funkcjonalnym, który można zastosować w LISP)? Czy po prostu zapomnę o grafach i rozwiązam problem w inny sposób?

Minęło trochę czasu, odkąd pracowałem w LISP, ale jak pamiętam, podstawową strukturą nieatomową jest lista. Wszystko inne opiera się na tym. Możesz mieć listę atomów, w której każdy atom jest węzłem, a następnie listę krawędzi łączących węzeł z innymi węzłami. Jestem pewien, że są też inne sposoby, aby to zrobić.

Może coś takiego:

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

może dać taki wykres:

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

Jeśli chcesz się spodobać, możesz również dodać do niego ciężary:

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

Może Cię to również zainteresować: Wykres CL (znaleziony podczas wyszukiwania w Google frazy „struktura wykresu lisp”)

Języki funkcjonalne traktują struktury danych w taki sam sposób jak języki niefunkcjonalne: oddzielając interfejs od implementacji, tworząc abstrakcyjne typy danych.

Możesz tworzyć abstrakcyjne typy danych w Lisp. Na przykład dla wykresu możesz chcieć mieć kilka funkcji:

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

Po utworzeniu tego interfejsu do wykresu możesz zaimplementować faktyczne struktury danych na wiele różnych sposobów, optymalizując takie czynniki, jak wydajność programisty, elastyczność i wydajność obliczeniowa.

Kluczem jest upewnienie się, że kod korzystający z grafów korzysta tylko z interfejsu grafów i nie ma dostępu do podstawowej implementacji. Dzięki temu kod klienta będzie prostszy, ponieważ zostanie odłączony od faktycznej implementacji.

Cóż, zależy to od tego, czy Twój wykres jest skierowany / niekierowany, ważony / nieważony, ale jednym ze sposobów przedstawienia ukierunkowanego, ważonego wykresu (który byłby najbardziej ogólny) jest mapa map (w Clojure)

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

reprezentuje mapę z węzłami: a: b i: c. : a wskazuje na: b o wadze 3 i: c o wadze 4.: b wskazuje na: a o wadze 1.: c nie wskazuje na nic.

W Common Lisp, gdybym musiał reprezentować drzewo, użyłbym albo listy (jeśli to tylko szybki hack), albo zdefiniowałbym klasę drzewa (lub struct, ale klasy dobrze współdziałają z funkcjami ogólnymi, więc czemu nie) .

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

Gdybym potrzebował dosłownych drzew w kodzie, prawdopodobnie zdefiniowałbym również make-treefunkcję, która pobiera reprezentację listy drzewa, którą chcę, i zamienia ją w drzewo obiektów drzewa.

W Haskell lista jest podstawową strukturą danych i jeśli chcesz bardziej zaawansowanych struktur danych, często używasz struktur rekurencyjnych, np. Drzewo ma wartość null lub węzeł i dwa drzewa

data Tree a = Null | Node Tree a Tree