1

这是带有标记节点和边的循环有向图的类型。

import qualified Data.Map as M
import Data.Foldable
import Data.Monoid

data Node n e = N n [(e, Node n e)]  -- the node's label and its list of neighbors
newtype Graph n e = G (M.Map n (Node n e))

为了处理图有循环的情况，可以“打结”并在有限空间中创建无限递归图。

type GraphInput n e = M.Map n [(e, n)]

mkGraph :: Ord n => GraphInput n e -> Graph n e
mkGraph spec = G $ nodeMap
    where nodeMap = M.mapWithKey mkNode (makeConsistent spec)
          -- mkNode :: n -> [(e, n)] -> Node n e
          mkNode lbl edges = N lbl $ map getEdge edges
          -- We know that (!) can't fail because we ensured that
          -- all edges have a key in the map (see makeConsistent)
          getEdge (e, lbl) = (e, nodeMap ! lbl)

makeConsistent :: Ord n => GraphInput n e -> GraphInput n e
makeConsistent m = foldr addMissing m nodesLinkedTo
    where addMissing el m = M.insertWith (\_ old -> old) el [] m
          nodesLinkedTo = map snd $ join $ M.elems m

通过将图形视为节点的集合，我们可以编写一个Foldable执行深度优先遍历的实例。*

newtype NodeGraph e n = NG {getNodeGraph :: Graph n e}

instance Foldable (NodeGraph e) where
    foldMap f (NG (G m)) = foldMap mapNode (M.elems m)
        where mapNode (N n es) = f n `mappend` foldMap mapEdge es
              mapEdge (e, n) = mapNode n

然而，即使对于简单的树形图，这也会产生重复的元素：

--   A
--  / \    X
-- B   C
--     |
--     D
ghci> let ng = NG $ mkGraph [('A', [(1, 'B'), (1, 'C')]), ('C', [(1, 'D')]), ('X', [])]
ghci> let toList = Data.Foldable.foldr (:) []
ghci> toList ng
"ABCDBCDDX"

当图形有循环时，效果更加显着——foldMap永远递归！循环中的项目是重复的，有些元素永远不会返回！

这个可以吗？一个实例可以Foldable多次返回它的一些元素，还是我违反了类的合同？实例可以在结构的一部分上无限循环吗？我一直在寻找关于这个问题的指导——我希望有一套“可折叠的法律”来解决这个问题——但我无法在网上找到任何关于这个问题的讨论。

摆脱这种情况的一种方法是“记住”在我遍历图表时已经访问过的元素。但是，这会给 的签名添加一个EqorOrd约束foldMap，这会阻止我的类型成为 的成员Foldable。

* 顺便说一下，我们不能为 编写一个Functor实例NodeGraph，因为它会破坏图中节点被唯一标记的不变性。（fmap (const "foo")例如，将每个节点重新标记为“foo”，尽管它们都有不同的边集！）我们可以（使用适当的newtype）编写一个Functor映射所有边标签的映射。

4

1 回答 1

3

目前法律很少Foldable，所以你可以做各种各样的事情。事实上，Foldable你可以编写几个不同的实例，对应不同的遍历顺序。这些Foldable定律描述了不同成员之间的关系Foldable，如果类型也是 a ，则还有一个与、和Functor相关的附加定律。foldfoldMapfmap

foldMap一些细节：关于, foldl, foldr,等之间的关系有一些简单的“法则” sum，只是说除了严格性之外，它们的行为应该与默认实现非常相似。因为fold，这个规律就是fold = foldMap id。如果容器也是Functor，则有一条法律规定您可以采用另一种方式：foldMap f = fold . fmap f. 正如我所说，没有什么太令人兴奋的了。

另一方面，我认为尝试将打结与独特的标签结合起来有点有趣。我不确定你在做什么，或者它是否真的有意义。在我看来，问题在于，尽管共享会导致图形在内存中随心所欲地表示，但这种共享根本没有反映在语言中。在 Haskell 中，带有循环的图看起来就像一棵无限树。事实上，对于不会（可能）将其变成无限树的循环图，您几乎无能为力。这就是为什么人们首先会费心使用诸如Data.Map表示图形之类的东西的原因——打结并不能提供图形结构的清晰视图。

于 2015-01-24T04:02:10.040 回答