haskell - Foldable は常にすべての結果を 1 回だけ返す必要がありますか?

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

グラフにループがある場合を処理するために、「結び目を結び」、有限空間で無限に再帰的なグラフを作成することができます。

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その要素の一部を複数回返すことができますか、それともクラスの契約に違反していますか? インスタンスは、構造の一部を無限にループできますか? 私はこの問題に関するガイダンスを探していました - 私は問題を解決する一連の「折り畳み式の法律」を望んでいました - しかし、オンラインで質問に関する議論を見つけることができませんでした.

---

この状況から抜け出すための 1 つの方法は、グラフをトラバースするときに既にアクセスした要素を「記憶」することです。ただし、これによりEqorOrdの署名に制約が追加foldMapされ、型が のメンバーになることができなくなりFoldableます。

_{Functor* ちなみに、 のインスタンスを書くことはできませんNodeGraph。グラフ内のノードが一意にラベル付けされるという不変条件が壊れてしまうからです。(fmap (const "foo")たとえば、 はすべてのノードを「foo」に再ラベル付けしますが、それらはすべて異なるエッジ セットを持ちます!) ただし、(適切な を使用して) すべてのエッジラベルをマップnewtypeする を記述できます。Functor}