如何在Haskell中定义二分图

Question

试图理解这些参数化类型如何在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]

为了使它更复杂，我想看看bipartite graph的定义是什么样的，基本上是一个包含两组节点的图，其中节点只连接到另一组的节点。

所以...（在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节点，我只是没有在示例中显示。

想知道如何在Haskell（或其他）中使用data或type正确定义它。

Answer 1

我会使用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