haskell - 广度优先树和深度优先树的 Traversable 是否不同？

Question

我有一个玫瑰树结构，我想写一个 Traversable 例如。所以我从以下几点开始:

data Tree a = Tree a [Tree a] deriving (Show)

instance Functor Tree where
  fmap f (Tree x subs) = Tree (f x) (fmap (fmap f) subs)

我做了它的深度优先变体:

newtype Depth a = Depth (Tree a) deriving (Show)

depth :: Tree a -> [a]
depth (Tree x subs) = x : concatMap depth subs

instance Functor Depth where
  fmap f (Depth t) = Depth $ fmap f t

instance Foldable Depth where
  foldMap f (Depth t) = mconcat $ f <$> depth t

instance Traversable Depth where
  traverse f (Depth t) = Depth <$> go t
    where go (Tree x subs) = Tree <$> f x <*> traverse go subs

然后我尝试了广度优先的变体:

newtype Breadth a = Breadth (Tree a) deriving (Show)

breadth :: Tree a -> [a]
breadth tree = go [tree]
  where
    go [] = []
    go (Tree x subs:q) = x : go (q <> subs)

instance Functor Breadth where
  fmap f (Breadth t) = Breadth $ fmap f t

instance Foldable Breadth where
  foldMap f (Breadth t) = mconcat $ f <$> breadth t

instance Traversable Breadth where
  traverse f (Breadth t) = ???

我意识到 Traversable 的广度和深度优先变体因为这应该是一样的。是这种情况吗？我不相信我真的在任何地方读过这个，但遍历与元素的顺序无关？

如果是这样，这就有点奇怪了，因为 Traversable然后可以直接为 Tree 实现，这意味着 Foldable需要为 Tree 实现，但显然有多种方式 Foldable可以实现。

Answer 1

Traversable不得不同意 Foldable .具体来说，如果 Monoid m ，然后 Applicative (Const m) ，导致一致性规律 foldMap f = getConst . traverse (Const . f) .因此 Breadth 是不可能的和 Depth分享一个Traversable . Traversable Breadth 有不同的实现同意其 Foldable ，或者根本没有。我可以制定一个我认为确实同意的实现方案，但我还没有验证其他法律。

instance Traversable Breadth where
  traverse f (Breadth t) = Breadth <$> head <$> go [t]
    where
      go [] = pure []
      go ts = zipWith Tree <$> traverse f rs
                           <*> (fmap (rebuild css) $ go $ concat css)
        where
          (rs, css) = unzip $ map (\(Tree r cs) -> (r, cs)) ts
          -- rebuild s d = evalState (traverse (state splitAt') d) s
          -- I think, but let's keep the dependencies down, shall we?
          rebuild [] [] = []
          rebuild (struct : structs) destruct
            = let (cs, destruct') = splitAt' struct destruct
              in  cs : rebuild structs destruct'
          -- ignoring the as in a [a] makes it look like a number
          splitAt' [] xs = ([], xs)
          splitAt' (_ : n) (x : xs)
            = let (pre, suf) = splitAt' n xs
              in  (x : pre, suf)

这是非常多毛的，而且到处都是非整体性，但它应该可以正常工作。