使用代数数据类型在 Haskell 中表示树或列表很容易。但是如何通过排版来表示图形呢？似乎你需要使用指针。我猜你可以这样做：
type Nodetag = String
type Neighbours = [Nodetag]
data Node a = Node a Nodetag Neighbours
这种方式是可行的，但感觉有点解耦；结构中不同节点之间的链接没有像列表中当前、前一个和后一个元素之间或树型结构中节点的父子之间那样紧密。我有一种直觉，通过我定义的标签系统对图进行代数操作可能会受到引入级别的间接性的阻碍。
主要是这种疑虑和感觉不够优雅，促使我提出这个问题。在Haskell中是否有更好/更数学优雅的定义图的方式？还是我碰到了什么困难/根本性的问题？递归数据结构很棒，但这似乎是另一回事。它与树和列表的自我引用不同。就像列表和树在类型层面上是自我引用的，而图在值层面上是自我引用的。
那么，到底发生了什么？
在shang的回答中，您可以看到如何使用惰性来表示图形。这些表示的问题在于它们非常难以更改。如果您只打算构建一次图形，然后永远不再更改，那么绑结技巧是有用的。
实际上，如果我想要对我的图进行操作，我会使用更加普通的表示方法：
如果您将频繁更改或编辑图形，则建议使用基于Huet's zipper的表示法。这是GHC在控制流图中内部使用的表示法。您可以在此处阅读有关它的信息：
我也发现在纯函数编程语言中，尝试表示具有循环结构的数据结构很麻烦。实际上循环结构是真正的问题，因为值可以共享，任何能够包含该类型成员(包括列表和树)的ADT都是DAG(有向无环图)。最根本的问题在于，如果有值A和B，A包含B，而B又包含A，那么在另一个存在之前，它们中的任何一个都无法创建。因为Haskell是惰性的，你可以使用一种称为"tying the knot" 的技巧来解决这个问题，但我觉得这样很困难(因为我还没有做过太多)。到目前为止，我的很多重要的编程工作都是在Mercury中完成的，而Mercury是严格的，所以打结并不起作用。
通常情况下，当我遇到这种情况时，我会采取额外的间接方式，就像你建议的那样；通常是使用一个从ID到实际元素的映射，并让元素包含对ID的引用，而不是对其他元素的引用。我不喜欢这种方法的主要原因是它感觉更加脆弱，引入了查找不存在的ID或将相同的ID分配给多个元素的可能性。当然，您可以编写代码以确保不会出现这些错误，甚至可以将其隐藏在抽象后面，使得这些错误可能发生的位置是有限的。但这仍然是一个容易出错的因素。
然而，快速搜索"Haskell图形"，我发现http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling，看起来很值得一读。
正如Ben所提到的，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
我们接受一个由(节点标签, [相邻标签])组成的列表，并通过一个中间查找列表(实际上是将节点连接起来)构建出实际的Node值。关键在于，nodeLookupList (其类型为[(a, Node a)])是使用mkNode构建的，而mkNode反过来又引用nodeLookupList以查找相邻的节点。
没错，图形不是代数的。要解决这个问题，你有几个选项：
Int）并直接引用它们，而不是代数地表示节点身份。通过使类型抽象并提供一个界面来为您摆弄间接引用，可以使此过程更加方便。例如，fgl和Hackage上的其他实用图库采取了这种方法。因此，每个选项都有其优缺点。选择最适合您的那个。
有一些人简单提到了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描述了一个多重图，其中节点和边缘具有标签，并且所有边缘都是有向的。Node具有某种类型a的标签；边缘具有某种类型b的标签。Context只是(1) 指向特定节点的带标签边缘列表， (2) 相应的节点， (3) 节点的标签，以及 (4) 指向节点的带标签边缘列表。因此，可以归纳地将Graph构想为Empty，或者作为已存在的Graph与&合并的Context。
正如Erwig所指出的，我们不能自由地使用Empty和&生成Graph，就像我们可能会使用Cons和Nil构造函数生成列表，或者使用Leaf和Branch生成Tree一样。同样，与列表不同（正如其他人所提到的），没有任何关于Graph的规范表示形式。这些是关键的差异。
尽管如此，使得这种表示如此强大并且与列表和树的典型Haskell表示非常相似的是，这里的Graph数据类型是归纳定义的。列表是归纳定义的事实使我们能够对其进行简洁的模式匹配，处理单个元素，并递归地处理列表的其余部分；同样，Erwig的归纳表示允许我们逐个Context递归地处理图形。
这种图的表示方式适合简单定义一种在图上映射的方法（gmap），以及执行无序图上的折叠的方法（ufold）。
本页中的其他评论很棒。然而，我写这篇答案的主要原因是当我读到诸如“图不是代数”的短语时，我担心一些读者将不可避免地产生这样的(错误)印象：没有人找到一种漂亮的方法来表示图形，在这种表示中允许对其进行模式匹配、映射、折叠，或者通常做我们通常用列表和树做的那种酷炫的函数式操作。
-- 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's 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)
我喜欢这个图的实现，它来自这里
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
fgl软件包是由此开发而来的。 - John L