haskell 广度优先树和深度优先树的可遍历性是否不同？

uwopmtnx 于 2022-11-14 发布在其他

关注(0)|答案(2)|浏览(223)

我有一个Rose Tree结构，我想为它写一个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。

haskell

来源：https://stackoverflow.com/questions/56519199/is-traversable-different-for-breadth-first-and-depth-first-trees

2条答案

按热度按时间

k3bvogb11#

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)

这是相当棘手的，而且到处都是非整体性，但它应该工作得很好。

赞(0）回复(0）举报 2022-11-14

z31licg02#

这里是HTNW解决方案的一个变体，使用Compose代替递归调用时的扁平化结构，这意味着我们不需要重建结构，但可能也会更慢，因为它需要在每个递归步骤遍历一个深层结构。
liftA2与ZipList一起被用于将zipWith推广到任意多个Compose d嵌套列表. ScopedTypeVariables被用于为多态递归函数go给予显式类型签名.

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
module BreadthFirstTraverse where
import Data.Tree (Tree(..))
import Control.Applicative (ZipList(..), Applicative (liftA2))
import Data.Functor.Compose (Compose(..))
-- import Control.Monad.Identity (Identity(..))

-- ...

instance Traversable Breadth where
  traverse f (Breadth t) = Breadth <$> bfTraverse f t

bfTraverse :: forall f a b. Applicative f => (a -> f b) -> Tree a -> f (Tree b)
bfTraverse k (Node t0 ts0) = nodeC <$> k t0 <*> go (ZipList ts0)
-- equivalent alternative: 
-- bfTraverse k t = fmap runIdentity (go (Identity t))
  where
    nodeC x xs = Node x (getZipList xs)
    go :: (Applicative t, Traversable t) => t (Tree a) -> f (t (Tree b))
    go ts | Just ts' <- nullMap ts = pure ts'
    go ts = liftA2 nodeC <$> traverse k rs <*> fmap getCompose (go $ Compose css)
        where
          rs = fmap rootLabel ts
          css = fmap (ZipList . subForest) ts

-- | If a structure is empty, replace its content type
-- > isJust . nullMap == null
nullMap :: Traversable t => t a -> Maybe (t b)
nullMap = traverse (const Nothing)

赞(0）回复(0）举报 2022-11-14

我来回答

haskell 广度优先树和深度优先树的可遍历性是否不同？

2条答案

相关问题

热门标签

最新问答