首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >对于广度优先和深度优先的树,可遍历是否不同?

对于广度优先和深度优先的树,可遍历是否不同?
EN

Stack Overflow用户
提问于 2019-06-10 07:57:06
回答 1查看 173关注 0票数 3

我有一个玫瑰树结构,我想为它写一个Traversable实例。因此,我从以下几点开始:

代码语言:javascript
复制
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)

我做了深度优先的变种:

代码语言:javascript
复制
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

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

代码语言:javascript
复制
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

EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56519199

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档