Как определить двудольный граф в Haskell - PullRequest
Новая
       7

Как определить двудольный граф в Haskell

0 голосов
/ 18 февраля 2019

Пытаясь понять, как эти параметризованные типы работают в Haskell, например: 

data List a = Nil | Cons a (List a)
data Either a b = Left a | Right b
data Tree a = Nil | Node a (Tree a) (Tree a)
data Tree = Branch [Tree]
data Tree a = Node a [Tree a]

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

Итак .. (в JavaScript) .... Пример того, как будут связаны данныевыглядит так: 

var typeA_node1 = { id: 'a1' }
var typeA_node2 = { id: 'a2' }
var typeA_node3 = { id: 'a3' }

var typeB_node1 = { id: 'b1' }
var typeB_node2 = { id: 'b2' }
var typeB_node3 = { id: 'b3' }

typeA_node1.right = typeB_node3
typeB_node3.right = typeA_node2

typeA_node2.right = typeB_node2
typeB_node2.right = typeA_node3

typeA_node3.right = typeB_node1

По сути, a--b--a--b--a--b--a--b, a всегда связан только с b, а не с a.a может быть подключен ко многим b узлам, я просто не показал этого в примере.

Хотите знать, как это правильно определить, используя data или type в Haskell (или что-то в этом роде?еще).

1 Ответ

0 голосов
/ 18 февраля 2019

Я бы использовал Data.Set для построения обоих наборов вершин и еще одного для ребер.Теперь оберните их в модуль, где вы их прячете.

module BiPartiteGraph (create) where


import qualified Data.Set as Set 


data BiPartiteGraph a = BiPartiteGraph (Set.Set a) (Set.Set a) (Set.Set (a, a)) -- (U, V, E)


-- Construct a BiPartiteGraph from a list of edges
create :: Ord a => [(a, a)] -> BiPartiteGraph a
create _ = undefined


-- Implementation of the show function 
instance (Show a) => Show (BiPartiteGraph a) where
    show _ = undefined
...