我有一个玫瑰树结构,我想为它写一个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
。
https://stackoverflow.com/questions/56519199
复制相似问题