Foldable 是否应该总是 return 它的所有结果恰好一次？

Question

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

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))

为了处理图有环的情况，它是possible到'tie the knot'并在有限space.

中创建无限递归图

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 永远递归！循环中的项目是重复的，有些元素永远不会 returned!

这样可以吗？ Foldable的一个实例可以return它的一些元素不止一次，还是我违反了class的约定？实例可以在结构的一部分上无限循环吗？我一直在寻找关于这个问题的指导 - 我希望有一组 'Foldable laws' 可以解决这个问题 - 但我无法在网上找到任何关于这个问题的讨论。

摆脱这种情况的一种方法是 'remember' 在我遍历图形时已经访问过的元素。但是，这会向 foldMap 的签名添加 Eq 或 Ord 约束，这会阻止我的类型成为 Foldable.

的成员

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

Answer 1

目前很少Foldable法律，所以你可以做各种各样的事情。事实上，您可以编写多个不同的 Foldable 实例，对应于不同的遍历顺序。 Foldable 法则描述了不同 Foldable 成员之间的关系，如果类型也是 Functor，则与 fold、foldMap 和 fmap.

一些细节：关于foldMap、foldl、foldr、sum等之间的关系有直接的"laws"，就是说除了严格性之外，它们的行为应该与它们的默认实现非常相似。对于fold，这个定律就是fold = foldMap id。如果容器也是Functor，则有一条定律规定你可以走另一条路：foldMap f = fold . fmap f。正如我所说，一点也不令人兴奋。

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

Foldable 是否应该总是 return 它的所有结果恰好一次？

Should a Foldable always return all its results exactly once?

haskell

graph

contract

typeclass

foldable