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?
Odpowiedzi:
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.