У меня есть структура 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
может быть реализовано несколькими способами.