Структуры данных в функциональном программировании

В настоящее время я играю с LISP (особенно Scheme и Clojure), и мне интересно, как обрабатываются типичные структуры данных в функциональных языках программирования.

Например, скажем, я хотел бы решить проблему, используя алгоритм поиска пути к графу. Как обычно можно представить этот граф на функциональном языке программирования (в первую очередь интересующемся чисто функциональным стилем, который можно применять к LISP)? Могу ли я просто забыть о графиках и решить проблему другим способом?

Я давно работал в LISP, но, насколько я помню, основная неатомарная структура - это список. Все остальное основано на этом. Таким образом, у вас может быть список атомов, где каждый атом является узлом, за которым следует список ребер, которые соединяют узел с другими узлами. Я уверен, что есть и другие способы сделать это тоже.

Может быть, что-то вроде этого:

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

мог бы дать такой график:

а <-> Ь <-> с <-> д
^ ^
| |
+ --------- +

Если вы хотите получить фантазию, вы также можете добавить к ней веса:

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

Возможно, вас заинтересует это: CL-Graph (найденный поиском в Google по фразе "lisp graph structure")

Функциональные языки работают со структурами данных так же, как нефункциональные языки: отделяя интерфейс от реализации, создавая абстрактные типы данных.

Вы можете создавать абстрактные типы данных в Лиспе. Например, для графа вам может потребоваться пара функций:

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

Создав этот интерфейс для графа, вы можете реализовать фактические структуры данных различными способами, возможно, оптимизируя такие факторы, как эффективность программиста, гибкость и вычислительная эффективность.

Ключ должен гарантировать, что код, который использует графики, использует только интерфейс графа и не имеет доступа к базовой реализации. Это сделает код клиента проще, поскольку он не связан с реальной реализацией.

Ну, это будет зависеть от того, является ли ваш граф направленным / ненаправленным, взвешенным / невзвешенным, но один способ представления ориентированного, взвешенного графа (который был бы наиболее общим) - с помощью карты карт (в Clojure)

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

будет представлять карту с узлами: a: b и: c. : a указывает на: b с весом 3 и: c с весом 4.: b указывает на: a с весом 1.: c ни на что не указывает.

В Common Lisp, если бы мне нужно было представить дерево, я бы использовал либо список (если бы он был просто для быстрого взлома), либо определял класс дерева (или структуру, но классы хорошо взаимодействуют с универсальными функциями, так почему бы и нет) ,

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

Если мне нужны литеральные деревья в коде, я бы, вероятно, также определил make-treeфункцию, которая принимает представление списка нужного мне дерева и превращает его в дерево объектов дерева.

В Haskell список является базовой структурой данных, и если вам нужны более сложные структуры данных, вы часто используете рекурсивные структуры, например, дерево является либо нулевым, либо узлом и двумя деревьями.

data Tree a = Null | Node Tree a Tree