import Prelude
#endif
+import Control.Applicative (Applicative(..))
import Control.Monad
+import Data.Monoid (Monoid(..))
import Data.Sequence (Seq, empty, singleton, (<|), (|>), fromList,
ViewL(..), ViewR(..), viewl, viewr)
-import qualified Data.Sequence as Seq (foldl)
+import Data.Foldable (Foldable(foldMap), toList)
+import Data.Traversable (Traversable(traverse))
import Data.Typeable
#include "Typeable.h"
mapTree :: (a -> b) -> (Tree a -> Tree b)
mapTree f (Node x ts) = Node (f x) (map (mapTree f) ts)
+instance Traversable Tree where
+ traverse f (Node x ts) = Node <$> f x <*> traverse (traverse f) ts
+
+instance Foldable Tree where
+ foldMap f (Node x ts) = f x `mappend` foldMap (foldMap f) ts
+
-- | Neat 2-dimensional drawing of a tree.
drawTree :: Tree String -> String
drawTree = unlines . draw
-- /Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design/,
-- by Chris Okasaki, /ICFP'00/.
unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
-unfoldForestM_BF f = liftM toRevList . unfoldForestQ f . fromList
- where toRevList :: Seq c -> [c]
- toRevList = Seq.foldl (flip (:)) []
+unfoldForestM_BF f = liftM toList . unfoldForestQ f . fromList
-- takes a sequence (queue) of seeds
-- produces a sequence (reversed queue) of trees of the same length