haskell - 如何为图声明数据构造函数

Question

下面我给出了列表和树的数据构造函数。

data List a = NilL | Cons a (List a) deriving Show
data Tree a = NilT | Branch a [Tree a] deriving Show

通过这些定义，我可以轻松创建无限结构，如下所示：

list = Cons 1 list
tree = Branch 1 lt
 where
  lt = tree : lt

我想以这种方式创建无限图（有向和无向）。如何为其声明数据构造函数以及如何在 Haskell 中使用该数据构造函数创建无限图？

Answer 1

一个简单的解决方案是使用某种形式的间接，例如索引

type Vertex = Integer
data Graph = Graph [Vertex] [(Vertex, Vertex)]

infGraph = Graph [1..] [(a, b) | a <- [1..], b <- [1..]]

然而，这并不像打结那样令人满意

data Vertex = Vertex { tag   :: Integer
                     , edges :: [Vertex] }

type Graph = [Vertex] -- A graph is determined by the set of vertices

-- Construct a graph of infinitely many vertices in which
-- each vertex is connected.
infGraph = map (flip Vertex infGraph) [1..]
infGraph' = map (\v' -> v' infGraph') . map Vertex $ [1..]

我们map Vertexover [1..]which 给了我们一个函数列表，[Vertex] -> Vertex这些函数需要一个边列表来连接每个顶点。由于infGraph是所有顶点的列表，我们将其传递给每个顶点Vertex并打结。

当然，对于认真的工作，请使用package。