如何在 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

如何在 Haskell 中定义二分图

How to define a bipartite graph in Haskell

haskell

graph

typeclass