Как вы представляете граф в Haskell?

Достаточно просто представить дерево или список в haskell, используя алгебраические типы данных. Но как бы вы представили график типографически? Похоже, вам нужны указатели. Я предполагаю, что у вас может быть что-то вроде

type Nodetag = String
type Neighbours = [Nodetag]
data Node a = Node a Nodetag Neighbours

И это было бы возможным. Однако он кажется немного разобщенным; Связи между различными узлами в структуре на самом деле не «кажутся» такими прочными, как связи между текущими предыдущим и следующим элементами в списке или родителями и потомками узла в дереве. У меня есть подозрение, что выполнение алгебраических манипуляций с графом, как я определил, будет несколько затруднено из-за уровня косвенности, вводимого через систему тегов.

Именно это чувство сомнения и ощущение неэлегантности заставляет меня задавать этот вопрос. Есть ли лучший / более математически элегантный способ определения графиков в Haskell? Или я наткнулся на что-то сложное / фундаментальное? Рекурсивные структуры данных хороши, но, похоже, это нечто другое. Самореференциальная структура данных в ином смысле, чем деревья и списки. Это похоже на то, что списки и деревья самореферентны на уровне типа, а графы самореферентны на уровне значений.

Так что же на самом деле происходит?

Мне также неудобно пытаться представить структуры данных с циклами на чистом языке. На самом деле проблема заключается в циклах; поскольку значения могут быть общими, любой ADT, который может содержать член типа (включая списки и деревья), на самом деле является DAG (направленным ациклическим графом). Основная проблема заключается в том, что если у вас есть значения A и B, где A содержит B, а B содержит A, то ни одно из них не может быть создано до того, как другое существует. Поскольку Haskell ленив, вы можете использовать уловку, известную как « Связывание узла», чтобы обойти это, но это причиняет боль моему мозгу (потому что я еще не сделал этого). До сих пор я делал больше программ на Mercury, чем на Haskell, и Mercury очень строг, поэтому завязывание узлов не помогает.

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

Однако быстрый поиск в Google "графика Haskell" привел меня к http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling , который, похоже, стоит прочитать.

В ответе Шанга вы можете увидеть, как представить график с помощью лени. Проблема с этими представлениями в том, что их очень трудно изменить. Уловка завязывания узлов полезна только в том случае, если вы собираетесь построить график один раз, а потом он никогда не изменится.

На практике, если я действительно хочу что- то сделать с моим графиком, я использую более простые представления:

• Список краев
• Список смежности
• Дайте уникальную метку каждому узлу, используйте метку вместо указателя и сохраните конечную карту от меток к узлам

Если вы собираетесь часто менять или редактировать график, я рекомендую использовать представление, основанное на застежке-молнии Хуэта. Это представление, используемое внутри GHC для графов потока управления. Вы можете прочитать об этом здесь:

• Аппликативный график потока управления на основе молнии Хуэта

• Hoopl: модульная многоразовая библиотека для анализа и преобразования потока данных

Как упоминал Бен, циклические данные в Haskell создаются с помощью механизма, называемого «связывание узла». На практике это означает, что мы пишем взаимно рекурсивные объявления с использованием предложений letили where, что работает, потому что взаимно рекурсивные части лениво вычисляются.

Вот пример типа графика:

import Data.Maybe (fromJust)

data Node a = Node
    { label    :: a
    , adjacent :: [Node a]
    }

data Graph a = Graph [Node a]

Как видите, мы используем реальные Nodeссылки вместо косвенных ссылок. Вот как реализовать функцию, которая строит график из списка ассоциаций меток.

mkGraph :: Eq a => [(a, [a])] -> Graph a
mkGraph links = Graph $ map snd nodeLookupList where

    mkNode (lbl, adj) = (lbl, Node lbl $ map lookupNode adj)

    nodeLookupList = map mkNode links

    lookupNode lbl = fromJust $ lookup lbl nodeLookupList

Мы берем список (nodeLabel, [adjacentLabel])пар и конструируем фактические Nodeзначения с помощью промежуточного справочного списка (который фактически связывает узлы). Хитрость в том, что nodeLookupList(имеющий тип [(a, Node a)]) создается с использованием mkNode, которое, в свою очередь, обращается к объекту nodeLookupListдля поиска соседних узлов.

Это правда, графы не алгебраические. Чтобы справиться с этой проблемой, у вас есть несколько вариантов:

1. Вместо графов рассмотрите бесконечные деревья. Представьте циклы в графе как их бесконечные развертки. В некоторых случаях вы можете использовать трюк, известный как «завязывание узла» (хорошо объясненный в некоторых других ответах здесь), чтобы даже представить эти бесконечные деревья в конечном пространстве, создав цикл в куче; однако вы не сможете наблюдать или обнаруживать эти циклы из Haskell, что делает различные операции с графами трудными или невозможными.
2. В литературе доступно множество алгебр графов. Первое, что приходит на ум в первую очередь, - это набор конструкторов графов, описанных во втором разделе « Преобразования двунаправленных графов» . Обычное свойство, гарантируемое этими алгебрами, состоит в том, что любой граф может быть представлен алгебраически; однако, что критически важно, многие графы не будут иметь канонического представления. Так что структурной проверки равенства недостаточно; правильное выполнение этой задачи сводится к поиску изоморфизма графов, что, как известно, является сложной проблемой.
3. Откажитесь от алгебраических типов данных; явно представлять идентичность узла, давая им уникальные значения (скажем, Ints) и ссылаясь на них косвенно, а не алгебраически. Это можно сделать значительно более удобным, если сделать тип абстрактным и предоставить интерфейс, который позволяет вам управлять косвенным обращением. Это подход, используемый, например, fgl и другими практическими библиотеками графов на Hackage.
4. Придумайте совершенно новый подход, который точно соответствует вашему варианту использования. Это очень непросто. знак равно

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

Некоторые другие вкратце упомянули fglи Индуктивные графы и функциональные графические алгоритмы Мартина Эрвига , но, вероятно, стоит написать ответ, который на самом деле дает представление о типах данных, лежащих в основе подхода индуктивного представления.

В своей статье Эрвиг представляет следующие типы:

type Node = Int
type Adj b = [(b, Node)]
type Context a b = (Adj b, Node, a, Adj b)
data Graph a b = Empty | Context a b & Graph a b

(Представление в fglнемного отличается и хорошо использует классы типов, но идея по сути та же.)

Эрвиг описывает мультиграф, в котором узлы и ребра имеют метки, и в котором все ребра направлены. A Nodeимеет метку некоторого типа a; ребро имеет метку какого-либо типа b. A Context- это просто (1) список помеченных ребер, указывающих на конкретный узел, (2) рассматриваемый узел, (3) метка узла и (4) список помеченных ребер, указывающих от узла. Тогда А Graphможно индуктивно представить как любое из них Emptyили как Contextслияние (с &) с существующим Graph.

Как Erwig заметки, мы не можем свободно генерировать Graphс Emptyи &, как мы могли бы создать список с Consи Nilконструкторами, или Treeс Leafи Branch. Кроме того, в отличие от списков (как уже упоминалось другими), не будет никакого канонического представления файла Graph. Это принципиальные различия.

Тем не менее, что делает это представление таким мощным и таким похожим на типичные представления списков и деревьев в Haskell, так это то, что Graphтип данных здесь определяется индуктивно . Тот факт, что список определен индуктивно, - это то, что позволяет нам так лаконично сопоставить его с шаблоном, обработать один элемент и рекурсивно обработать остальную часть списка; в равной степени индуктивное представление Эрвига позволяет нам рекурсивно обрабатывать граф по одному Context. Это представление графа поддается простому определению способа сопоставления по графу ( gmap), а также способа выполнения неупорядоченных сверток над графами ( ufold).

Остальные комментарии на этой странице великолепны. Однако основная причина, по которой я написал этот ответ, заключается в том, что, когда я читаю такие фразы, как «графы не алгебраические», я боюсь, что у некоторых читателей неизбежно сложится (ошибочное) впечатление, что никто не нашел хорошего способа представления графов. в Haskell таким образом, чтобы разрешить для них сопоставление с образцом, сопоставление с ними, их сворачивание или вообще то, что мы привыкли делать со списками и деревьями.

Мне всегда нравился подход Мартина Эрвига в статье «Индуктивные графы и функциональные графические алгоритмы», которые вы можете прочитать здесь . FWIW, однажды я тоже написал реализацию Scala, см. Https://github.com/nicolast/scalagraphs .

Любое обсуждение представления графов в Haskell требует упоминания библиотеки преобразования данных Энди Гилла (вот статья ).

Представление в стиле «завязывание узла» можно использовать для создания очень элегантных DSL (см. Пример ниже). Однако использование структуры данных ограничено. Библиотека Гилла позволяет вам использовать лучшее из обоих миров. Вы можете использовать DSL, который «связывает узел», но затем преобразовать граф, основанный на указателях, в граф на основе меток, чтобы вы могли запускать на нем свои алгоритмы.

Вот простой пример:

-- Graph we want to represent:
--    .----> a <----.
--   /               \
--  b <------------.  \
--   \              \ / 
--    `----> c ----> d

-- Code for the graph:
a = leaf
b = node2 a c
c = node1 d
d = node2 a b
-- Yes, it's that simple!



-- If you want to convert the graph to a Node-Label format:
main = do
    g <- reifyGraph b   --can't use 'a' because not all nodes are reachable
    print g

Для запуска приведенного выше кода вам потребуются следующие определения:

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
import Data.Reify
import Control.Applicative
import Data.Traversable

--Pointer-based graph representation
data PtrNode = PtrNode [PtrNode]

--Label-based graph representation
data LblNode lbl = LblNode [lbl] deriving Show

--Convenience functions for our DSL
leaf      = PtrNode []
node1 a   = PtrNode [a]
node2 a b = PtrNode [a, b]


-- This looks scary but we're just telling data-reify where the pointers are
-- in our graph representation so they can be turned to labels
instance MuRef PtrNode where
    type DeRef PtrNode = LblNode
    mapDeRef f (PtrNode as) = LblNode <$> (traverse f as)

Я хочу подчеркнуть, что это упрощенный DSL, но нет предела! Я разработал очень функциональный DSL, включая красивый древовидный синтаксис для передачи узлом начального значения некоторым своим дочерним элементам, а также множество вспомогательных функций для создания определенных типов узлов. Конечно, гораздо сложнее были задействованы тип данных Node и определения mapDeRef.

Мне нравится эта реализация графика, взятого отсюда

import Data.Maybe
import Data.Array

class Enum b => Graph a b | a -> b where
    vertices ::  a -> [b]
    edge :: a -> b -> b -> Maybe Double
    fromInt :: a -> Int -> b