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

Ответ 1

Мне также неудобно пытаться представлять структуры данных с циклами на чистом языке. Это циклы, которые действительно являются проблемой; потому что значения могут быть разделены любым ADT, который может содержать член типа (включая списки и деревья), на самом деле представляет собой DAG (Direct Acitlic Graph). Основная проблема заключается в том, что если у вас есть значения A и B, с A, содержащими B и B, содержащими A, то они не могут быть созданы до того, как существовать другое. Поскольку Haskell ленив, вы можете использовать трюк, известный как Tying the Knot, чтобы обойти это, но это заставляет мой мозг болеть (потому что я еще не сделал много этого). Я сделал больше своих существенных программ в Mercury, чем Haskell, и Mercury строг, поэтому привязка узлов не помогает.

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

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

Ответ 2

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

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

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

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

• Прикладной график потока управления на основе Huet Zipper

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

Ответ 3

Как упоминал Бен, циклические данные в 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, чтобы найти соседние узлы.

Ответ 4

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

• Вместо графиков рассмотрим бесконечные деревья. Представляем циклы в графе как их бесконечные развертки. В некоторых случаях вы можете использовать трюк, известный как "связывание узла" (хорошо объясненный в некоторых других ответах здесь), чтобы даже представить эти бесконечные деревья в конечном пространстве, создав цикл в куче; однако вы не сможете наблюдать или обнаруживать эти циклы изнутри Haskell, что затрудняет или делает невозможным выполнение различных операций с графиком.
• В литературе имеется множество алгебр графов. Первое, что приходит на ум, - это сборник конструкторов графов, описанных в разделе 2 Двунаправленных преобразований графа. Обычное свойство, гарантируемое этими алгебрами, состоит в том, что любой граф может быть представлен алгебраически; однако критически многие графики не будут иметь канонического представления. Поэтому проверки равенства структурно недостаточно; делать это правильно сводится к поиску изоморфизма графов, который, как известно, является чем-то серьезным.
• Откажитесь от алгебраических типов данных; явно представляют идентификатор node, предоставляя им каждое уникальное значение (например, Int s) и ссылаясь на них косвенно, а не алгебраически. Это можно сделать значительно более удобным, сделав абстрактный тип и предоставив интерфейс, который жонглирует косвенностью для вас. Это подход, используемый, например, fgl и другими практическими библиотеками графов в Hackage.
• Придумайте совершенно новый подход, который подходит именно вам. Это очень сложно сделать. =)

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

Ответ 5

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

Ответ 6

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

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

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 немного отличается и хорошо использует классы типов, но идея по существу одинакова.)

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

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

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

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

Ответ 7

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

Представление стиля "привязка к узлу" может использоваться для создания очень элегантных DSL (см. пример ниже). Однако структура данных ограничена. Библиотека Gill дает вам лучшее из обоих миров. Вы можете использовать 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 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 транслировал начальную значение для некоторых его дочерних элементов и множество удобных функций для построения конкретных типов node. Конечно, определения типа данных node и mapDeRef были гораздо более сложными.

Ответ 8

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

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