{-# OPTIONS_GHC -Wno-name-shadowing #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Data.Traversable.TreeLike
( TreeLike(..), treeFoldMap
, Forest(..), Flat(..), List(..)
, inorder, preorder, postorder, levelorder, rlevelorder
, InOrder(..), PreOrder(..), PostOrder(..), LevelOrder(..), RLevelOrder(..)
, showTree, printTree
) where
import Data.Functor.Compose (Compose(..))
import Data.Functor.Const (Const(..))
import Data.Functor.Product (Product(..))
import Data.Functor.Sum (Sum(..))
import Data.Traversable (foldMapDefault)
import Data.Tree hiding (Forest)
import Control.Applicative.Phases
import Data.BinaryTree
import Data.Monoid.TreeDiagram
showTree :: (TreeLike tree, Show a) => tree a -> ShowS
showTree :: forall (tree :: * -> *) a.
(TreeLike tree, Show a) =>
tree a -> ShowS
showTree = TreeDiagram -> ShowS
showTreeDiagram (TreeDiagram -> ShowS)
-> (tree a -> TreeDiagram) -> tree a -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> TreeDiagram)
-> (TreeDiagram -> TreeDiagram) -> tree a -> TreeDiagram
forall m (tree :: * -> *) a.
(Monoid m, TreeLike tree) =>
(a -> m) -> (m -> m) -> tree a -> m
treeFoldMap a -> TreeDiagram
forall a. Show a => a -> TreeDiagram
singleton TreeDiagram -> TreeDiagram
subtree
printTree :: (TreeLike tree, Show a) => tree a -> IO ()
printTree :: forall (tree :: * -> *) a.
(TreeLike tree, Show a) =>
tree a -> IO ()
printTree = String -> IO ()
putStrLn (String -> IO ()) -> (tree a -> String) -> tree a -> IO ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ []) (ShowS -> String) -> (tree a -> ShowS) -> tree a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. tree a -> ShowS
forall (tree :: * -> *) a.
(TreeLike tree, Show a) =>
tree a -> ShowS
showTree
class Functor tree => TreeLike tree where
treeTraverse :: Applicative f
=> (a -> f b)
-> (forall subtree. TreeLike subtree => subtree a -> f (subtree b))
-> tree a -> f (tree b)
treeFoldMap :: (Monoid m, TreeLike tree) => (a -> m) -> (m -> m) -> tree a -> m
treeFoldMap :: forall m (tree :: * -> *) a.
(Monoid m, TreeLike tree) =>
(a -> m) -> (m -> m) -> tree a -> m
treeFoldMap a -> m
f m -> m
g = Const m (tree Any) -> m
forall {k} a (b :: k). Const a b -> a
getConst (Const m (tree Any) -> m)
-> (tree a -> Const m (tree Any)) -> tree a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Const m Any)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> Const m (subtree Any))
-> tree a
-> Const m (tree Any)
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
treeTraverse (m -> Const m Any
forall {k} a (b :: k). a -> Const a b
Const (m -> Const m Any) -> (a -> m) -> a -> Const m Any
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> m
f) (m -> Const m (subtree Any)
forall {k} a (b :: k). a -> Const a b
Const (m -> Const m (subtree Any))
-> (subtree a -> m) -> subtree a -> Const m (subtree Any)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> m
g (m -> m) -> (subtree a -> m) -> subtree a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m) -> (m -> m) -> subtree a -> m
forall m (tree :: * -> *) a.
(Monoid m, TreeLike tree) =>
(a -> m) -> (m -> m) -> tree a -> m
treeFoldMap a -> m
f m -> m
g)
instance TreeLike Tree where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> Tree a
-> f (Tree b)
treeTraverse a -> f b
f forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (Node a
a [Tree a]
as) = b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node (b -> [Tree b] -> Tree b) -> f b -> f ([Tree b] -> Tree b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a f ([Tree b] -> Tree b) -> f [Tree b] -> f (Tree b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (Tree a -> f (Tree b)) -> [Tree a] -> f [Tree b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse Tree a -> f (Tree b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g [Tree a]
as
instance TreeLike BinaryTree where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> BinaryTree a
-> f (BinaryTree b)
treeTraverse a -> f b
_ forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
_ BinaryTree a
Leaf = BinaryTree b -> f (BinaryTree b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure BinaryTree b
forall a. BinaryTree a
Leaf
treeTraverse a -> f b
f forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (Branch BinaryTree a
l a
a BinaryTree a
r) = BinaryTree b -> b -> BinaryTree b -> BinaryTree b
forall a. BinaryTree a -> a -> BinaryTree a -> BinaryTree a
Branch (BinaryTree b -> b -> BinaryTree b -> BinaryTree b)
-> f (BinaryTree b) -> f (b -> BinaryTree b -> BinaryTree b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> BinaryTree a -> f (BinaryTree b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g BinaryTree a
l f (b -> BinaryTree b -> BinaryTree b)
-> f b -> f (BinaryTree b -> BinaryTree b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> a -> f b
f a
a f (BinaryTree b -> BinaryTree b)
-> f (BinaryTree b) -> f (BinaryTree b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> BinaryTree a -> f (BinaryTree b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g BinaryTree a
r
instance (TreeLike fst, TreeLike snd) => TreeLike (Product fst snd) where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> Product fst snd a
-> f (Product fst snd b)
treeTraverse a -> f b
_ forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (Pair fst a
x snd a
y) = fst b -> snd b -> Product fst snd b
forall {k} (f :: k -> *) (g :: k -> *) (a :: k).
f a -> g a -> Product f g a
Pair (fst b -> snd b -> Product fst snd b)
-> f (fst b) -> f (snd b -> Product fst snd b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> fst a -> f (fst b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g fst a
x f (snd b -> Product fst snd b)
-> f (snd b) -> f (Product fst snd b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> snd a -> f (snd b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g snd a
y
instance (TreeLike left, TreeLike right) => TreeLike (Sum left right) where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> Sum left right a
-> f (Sum left right b)
treeTraverse a -> f b
_ forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (InL left a
x) = left b -> Sum left right b
forall {k} (f :: k -> *) (g :: k -> *) (a :: k). f a -> Sum f g a
InL (left b -> Sum left right b) -> f (left b) -> f (Sum left right b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> left a -> f (left b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g left a
x
treeTraverse a -> f b
_ forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (InR right a
y) = right b -> Sum left right b
forall {k} (f :: k -> *) (g :: k -> *) (a :: k). g a -> Sum f g a
InR (right b -> Sum left right b)
-> f (right b) -> f (Sum left right b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> right a -> f (right b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g right a
y
newtype Forest t tree a = Forest { forall (t :: * -> *) (tree :: * -> *) a.
Forest t tree a -> t (tree a)
getForest :: t (tree a) }
deriving (forall a b. (a -> b) -> Forest t tree a -> Forest t tree b)
-> (forall a b. a -> Forest t tree b -> Forest t tree a)
-> Functor (Forest t tree)
forall a b. a -> Forest t tree b -> Forest t tree a
forall a b. (a -> b) -> Forest t tree a -> Forest t tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
forall (t :: * -> *) (tree :: * -> *) a b.
(Functor t, Functor tree) =>
a -> Forest t tree b -> Forest t tree a
forall (t :: * -> *) (tree :: * -> *) a b.
(Functor t, Functor tree) =>
(a -> b) -> Forest t tree a -> Forest t tree b
$cfmap :: forall (t :: * -> *) (tree :: * -> *) a b.
(Functor t, Functor tree) =>
(a -> b) -> Forest t tree a -> Forest t tree b
fmap :: forall a b. (a -> b) -> Forest t tree a -> Forest t tree b
$c<$ :: forall (t :: * -> *) (tree :: * -> *) a b.
(Functor t, Functor tree) =>
a -> Forest t tree b -> Forest t tree a
<$ :: forall a b. a -> Forest t tree b -> Forest t tree a
Functor
instance (Traversable t, TreeLike tree) => TreeLike (Forest t tree) where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> Forest t tree a
-> f (Forest t tree b)
treeTraverse a -> f b
_ forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g = (t (tree b) -> Forest t tree b)
-> f (t (tree b)) -> f (Forest t tree b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap t (tree b) -> Forest t tree b
forall (t :: * -> *) (tree :: * -> *) a.
t (tree a) -> Forest t tree a
Forest (f (t (tree b)) -> f (Forest t tree b))
-> (Forest t tree a -> f (t (tree b)))
-> Forest t tree a
-> f (Forest t tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (tree a -> f (tree b)) -> t (tree a) -> f (t (tree b))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b)
traverse tree a -> f (tree b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (t (tree a) -> f (t (tree b)))
-> (Forest t tree a -> t (tree a))
-> Forest t tree a
-> f (t (tree b))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Forest t tree a -> t (tree a)
forall (t :: * -> *) (tree :: * -> *) a.
Forest t tree a -> t (tree a)
getForest
newtype List a = List { forall a. List a -> [a]
getList :: [a] }
deriving (forall a b. (a -> b) -> List a -> List b)
-> (forall a b. a -> List b -> List a) -> Functor List
forall a b. a -> List b -> List a
forall a b. (a -> b) -> List a -> List b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> List a -> List b
fmap :: forall a b. (a -> b) -> List a -> List b
$c<$ :: forall a b. a -> List b -> List a
<$ :: forall a b. a -> List b -> List a
Functor
instance TreeLike List where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> List a
-> f (List b)
treeTraverse a -> f b
f forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (List [a]
as) = [b] -> List b
forall a. [a] -> List a
List ([b] -> List b) -> f [b] -> f (List b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> case [a]
as of
[] -> [b] -> f [b]
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure []
a
a:[a]
as -> (:) (b -> [b] -> [b]) -> f b -> f ([b] -> [b])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a f ([b] -> [b]) -> f [b] -> f [b]
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> ((List b -> [b]) -> f (List b) -> f [b]
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap List b -> [b]
forall a. List a -> [a]
getList (f (List b) -> f [b]) -> ([a] -> f (List b)) -> [a] -> f [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List a -> f (List b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (List a -> f (List b)) -> ([a] -> List a) -> [a] -> f (List b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.[a] -> List a
forall a. [a] -> List a
List) [a]
as
newtype Flat t a = Flat { forall (t :: * -> *) a. Flat t a -> t a
getFlat :: t a }
deriving (forall a b. (a -> b) -> Flat t a -> Flat t b)
-> (forall a b. a -> Flat t b -> Flat t a) -> Functor (Flat t)
forall a b. a -> Flat t b -> Flat t a
forall a b. (a -> b) -> Flat t a -> Flat t b
forall (t :: * -> *) a b. Functor t => a -> Flat t b -> Flat t a
forall (t :: * -> *) a b.
Functor t =>
(a -> b) -> Flat t a -> Flat t b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (t :: * -> *) a b.
Functor t =>
(a -> b) -> Flat t a -> Flat t b
fmap :: forall a b. (a -> b) -> Flat t a -> Flat t b
$c<$ :: forall (t :: * -> *) a b. Functor t => a -> Flat t b -> Flat t a
<$ :: forall a b. a -> Flat t b -> Flat t a
Functor
instance Traversable t => TreeLike (Flat t) where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> Flat t a
-> f (Flat t b)
treeTraverse a -> f b
f forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
_ (Flat t a
ta) = t b -> Flat t b
forall (t :: * -> *) a. t a -> Flat t a
Flat (t b -> Flat t b) -> f (t b) -> f (Flat t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f t a
ta
instance (TreeLike outer, TreeLike inner) => TreeLike (Compose outer inner) where
treeTraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> Compose outer inner a
-> f (Compose outer inner b)
treeTraverse a -> f b
_ forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (Compose outer (inner a)
trees) = outer (inner b) -> Compose outer inner b
forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose (outer (inner b) -> Compose outer inner b)
-> f (outer (inner b)) -> f (Compose outer inner b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (inner a -> f (inner b))
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree (inner a) -> f (subtree (inner b)))
-> outer (inner a)
-> f (outer (inner b))
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> outer a
-> f (outer b)
treeTraverse inner a -> f (inner b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g ((Compose subtree inner b -> subtree (inner b))
-> f (Compose subtree inner b) -> f (subtree (inner b))
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Compose subtree inner b -> subtree (inner b)
forall {k1} {k2} (f :: k1 -> *) (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose (f (Compose subtree inner b) -> f (subtree (inner b)))
-> (subtree (inner a) -> f (Compose subtree inner b))
-> subtree (inner a)
-> f (subtree (inner b))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compose subtree inner a -> f (Compose subtree inner b)
forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b)
g (Compose subtree inner a -> f (Compose subtree inner b))
-> (subtree (inner a) -> Compose subtree inner a)
-> subtree (inner a)
-> f (Compose subtree inner b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. subtree (inner a) -> Compose subtree inner a
forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose) outer (inner a)
trees
inorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
inorder :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
inorder a -> f b
f = (a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
treeTraverse a -> f b
f ((a -> f b) -> subtree a -> f (subtree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
inorder a -> f b
f)
preorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
preorder :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
preorder a -> f b
f = Phases f (tree b) -> f (tree b)
forall (f :: * -> *) a. Applicative f => Phases f a -> f a
runPhasesForwards (Phases f (tree b) -> f (tree b))
-> (tree a -> Phases f (tree b)) -> tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Phases f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> Phases f (subtree b))
-> tree a
-> Phases f (tree b)
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
treeTraverse (f b -> Phases f b
forall (f :: * -> *) a. f a -> Phases f a
now (f b -> Phases f b) -> (a -> f b) -> a -> Phases f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f b
f) (f (subtree b) -> Phases f (subtree b)
forall (f :: * -> *) a. Applicative f => f a -> Phases f a
later (f (subtree b) -> Phases f (subtree b))
-> (subtree a -> f (subtree b))
-> subtree a
-> Phases f (subtree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> subtree a -> f (subtree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
preorder a -> f b
f)
postorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
postorder :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
postorder a -> f b
f = Phases f (tree b) -> f (tree b)
forall (f :: * -> *) a. Applicative f => Phases f a -> f a
runPhasesBackwards (Phases f (tree b) -> f (tree b))
-> (tree a -> Phases f (tree b)) -> tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Phases f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> Phases f (subtree b))
-> tree a
-> Phases f (tree b)
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
treeTraverse (f b -> Phases f b
forall (f :: * -> *) a. f a -> Phases f a
now (f b -> Phases f b) -> (a -> f b) -> a -> Phases f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f b
f) (f (subtree b) -> Phases f (subtree b)
forall (f :: * -> *) a. Applicative f => f a -> Phases f a
later (f (subtree b) -> Phases f (subtree b))
-> (subtree a -> f (subtree b))
-> subtree a
-> Phases f (subtree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> subtree a -> f (subtree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
postorder a -> f b
f)
levelorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
levelorder :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
levelorder = \a -> f b
f -> Phases f (tree b) -> f (tree b)
forall (f :: * -> *) a. Applicative f => Phases f a -> f a
runPhasesForwards (Phases f (tree b) -> f (tree b))
-> (tree a -> Phases f (tree b)) -> tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> Phases f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> Phases f (tree b)
schedule a -> f b
f where
schedule :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> Phases f (tree b)
schedule :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> Phases f (tree b)
schedule a -> f b
f = (a -> Phases f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> Phases f (subtree b))
-> tree a
-> Phases f (tree b)
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
treeTraverse (f b -> Phases f b
forall (f :: * -> *) a. f a -> Phases f a
now (f b -> Phases f b) -> (a -> f b) -> a -> Phases f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f b
f) (Phases f (subtree b) -> Phases f (subtree b)
forall (f :: * -> *) a. Applicative f => Phases f a -> Phases f a
delay (Phases f (subtree b) -> Phases f (subtree b))
-> (subtree a -> Phases f (subtree b))
-> subtree a
-> Phases f (subtree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> subtree a -> Phases f (subtree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> Phases f (tree b)
schedule a -> f b
f)
rlevelorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
rlevelorder :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
rlevelorder = \a -> f b
f -> Phases f (tree b) -> f (tree b)
forall (f :: * -> *) a. Applicative f => Phases f a -> f a
runPhasesBackwards (Phases f (tree b) -> f (tree b))
-> (tree a -> Phases f (tree b)) -> tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> Phases f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> Phases f (tree b)
schedule a -> f b
f where
schedule :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> Phases f (tree b)
schedule :: forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> Phases f (tree b)
schedule a -> f b
f = (a -> Phases f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> Phases f (subtree b))
-> tree a
-> Phases f (tree b)
forall (tree :: * -> *) (f :: * -> *) a b.
(TreeLike tree, Applicative f) =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> (forall (subtree :: * -> *).
TreeLike subtree =>
subtree a -> f (subtree b))
-> tree a
-> f (tree b)
treeTraverse (f b -> Phases f b
forall (f :: * -> *) a. f a -> Phases f a
now (f b -> Phases f b) -> (a -> f b) -> a -> Phases f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f b
f) (Phases f (subtree b) -> Phases f (subtree b)
forall (f :: * -> *) a. Applicative f => Phases f a -> Phases f a
delay (Phases f (subtree b) -> Phases f (subtree b))
-> (subtree a -> Phases f (subtree b))
-> subtree a
-> Phases f (subtree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> subtree a -> Phases f (subtree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> Phases f (tree b)
schedule a -> f b
f)
newtype InOrder tree a = InOrder { forall (tree :: * -> *) a. InOrder tree a -> tree a
getInOrder :: tree a }
deriving (forall a b. (a -> b) -> InOrder tree a -> InOrder tree b)
-> (forall a b. a -> InOrder tree b -> InOrder tree a)
-> Functor (InOrder tree)
forall a b. a -> InOrder tree b -> InOrder tree a
forall a b. (a -> b) -> InOrder tree a -> InOrder tree b
forall (tree :: * -> *) a b.
Functor tree =>
a -> InOrder tree b -> InOrder tree a
forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> InOrder tree a -> InOrder tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> InOrder tree a -> InOrder tree b
fmap :: forall a b. (a -> b) -> InOrder tree a -> InOrder tree b
$c<$ :: forall (tree :: * -> *) a b.
Functor tree =>
a -> InOrder tree b -> InOrder tree a
<$ :: forall a b. a -> InOrder tree b -> InOrder tree a
Functor
instance TreeLike tree => Foldable (InOrder tree) where
foldMap :: forall m a. Monoid m => (a -> m) -> InOrder tree a -> m
foldMap = (a -> m) -> InOrder tree a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault
instance TreeLike tree => Traversable (InOrder tree) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> InOrder tree a -> f (InOrder tree b)
traverse a -> f b
f = (tree b -> InOrder tree b) -> f (tree b) -> f (InOrder tree b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap tree b -> InOrder tree b
forall (tree :: * -> *) a. tree a -> InOrder tree a
InOrder (f (tree b) -> f (InOrder tree b))
-> (InOrder tree a -> f (tree b))
-> InOrder tree a
-> f (InOrder tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
inorder a -> f b
f (tree a -> f (tree b))
-> (InOrder tree a -> tree a) -> InOrder tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InOrder tree a -> tree a
forall (tree :: * -> *) a. InOrder tree a -> tree a
getInOrder
newtype PreOrder tree a = PreOrder { forall (tree :: * -> *) a. PreOrder tree a -> tree a
getPreOrder :: tree a }
deriving (forall a b. (a -> b) -> PreOrder tree a -> PreOrder tree b)
-> (forall a b. a -> PreOrder tree b -> PreOrder tree a)
-> Functor (PreOrder tree)
forall a b. a -> PreOrder tree b -> PreOrder tree a
forall a b. (a -> b) -> PreOrder tree a -> PreOrder tree b
forall (tree :: * -> *) a b.
Functor tree =>
a -> PreOrder tree b -> PreOrder tree a
forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> PreOrder tree a -> PreOrder tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> PreOrder tree a -> PreOrder tree b
fmap :: forall a b. (a -> b) -> PreOrder tree a -> PreOrder tree b
$c<$ :: forall (tree :: * -> *) a b.
Functor tree =>
a -> PreOrder tree b -> PreOrder tree a
<$ :: forall a b. a -> PreOrder tree b -> PreOrder tree a
Functor
instance TreeLike tree => Foldable (PreOrder tree) where
foldMap :: forall m a. Monoid m => (a -> m) -> PreOrder tree a -> m
foldMap = (a -> m) -> PreOrder tree a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault
instance TreeLike tree => Traversable (PreOrder tree) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PreOrder tree a -> f (PreOrder tree b)
traverse a -> f b
f = (tree b -> PreOrder tree b) -> f (tree b) -> f (PreOrder tree b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap tree b -> PreOrder tree b
forall (tree :: * -> *) a. tree a -> PreOrder tree a
PreOrder (f (tree b) -> f (PreOrder tree b))
-> (PreOrder tree a -> f (tree b))
-> PreOrder tree a
-> f (PreOrder tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
preorder a -> f b
f (tree a -> f (tree b))
-> (PreOrder tree a -> tree a) -> PreOrder tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PreOrder tree a -> tree a
forall (tree :: * -> *) a. PreOrder tree a -> tree a
getPreOrder
newtype PostOrder tree a = PostOrder { forall (tree :: * -> *) a. PostOrder tree a -> tree a
getPostOrder :: tree a }
deriving (forall a b. (a -> b) -> PostOrder tree a -> PostOrder tree b)
-> (forall a b. a -> PostOrder tree b -> PostOrder tree a)
-> Functor (PostOrder tree)
forall a b. a -> PostOrder tree b -> PostOrder tree a
forall a b. (a -> b) -> PostOrder tree a -> PostOrder tree b
forall (tree :: * -> *) a b.
Functor tree =>
a -> PostOrder tree b -> PostOrder tree a
forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> PostOrder tree a -> PostOrder tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> PostOrder tree a -> PostOrder tree b
fmap :: forall a b. (a -> b) -> PostOrder tree a -> PostOrder tree b
$c<$ :: forall (tree :: * -> *) a b.
Functor tree =>
a -> PostOrder tree b -> PostOrder tree a
<$ :: forall a b. a -> PostOrder tree b -> PostOrder tree a
Functor
instance TreeLike tree => Foldable (PostOrder tree) where
foldMap :: forall m a. Monoid m => (a -> m) -> PostOrder tree a -> m
foldMap = (a -> m) -> PostOrder tree a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault
instance TreeLike tree => Traversable (PostOrder tree) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PostOrder tree a -> f (PostOrder tree b)
traverse a -> f b
f = (tree b -> PostOrder tree b) -> f (tree b) -> f (PostOrder tree b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap tree b -> PostOrder tree b
forall (tree :: * -> *) a. tree a -> PostOrder tree a
PostOrder (f (tree b) -> f (PostOrder tree b))
-> (PostOrder tree a -> f (tree b))
-> PostOrder tree a
-> f (PostOrder tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
postorder a -> f b
f (tree a -> f (tree b))
-> (PostOrder tree a -> tree a) -> PostOrder tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PostOrder tree a -> tree a
forall (tree :: * -> *) a. PostOrder tree a -> tree a
getPostOrder
newtype LevelOrder tree a = LevelOrder { forall (tree :: * -> *) a. LevelOrder tree a -> tree a
getLevelOrder :: tree a }
deriving (forall a b. (a -> b) -> LevelOrder tree a -> LevelOrder tree b)
-> (forall a b. a -> LevelOrder tree b -> LevelOrder tree a)
-> Functor (LevelOrder tree)
forall a b. a -> LevelOrder tree b -> LevelOrder tree a
forall a b. (a -> b) -> LevelOrder tree a -> LevelOrder tree b
forall (tree :: * -> *) a b.
Functor tree =>
a -> LevelOrder tree b -> LevelOrder tree a
forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> LevelOrder tree a -> LevelOrder tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> LevelOrder tree a -> LevelOrder tree b
fmap :: forall a b. (a -> b) -> LevelOrder tree a -> LevelOrder tree b
$c<$ :: forall (tree :: * -> *) a b.
Functor tree =>
a -> LevelOrder tree b -> LevelOrder tree a
<$ :: forall a b. a -> LevelOrder tree b -> LevelOrder tree a
Functor
instance TreeLike tree => Foldable (LevelOrder tree) where
foldMap :: forall m a. Monoid m => (a -> m) -> LevelOrder tree a -> m
foldMap = (a -> m) -> LevelOrder tree a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault
instance TreeLike tree => Traversable (LevelOrder tree) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> LevelOrder tree a -> f (LevelOrder tree b)
traverse a -> f b
f = (tree b -> LevelOrder tree b)
-> f (tree b) -> f (LevelOrder tree b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap tree b -> LevelOrder tree b
forall (tree :: * -> *) a. tree a -> LevelOrder tree a
LevelOrder (f (tree b) -> f (LevelOrder tree b))
-> (LevelOrder tree a -> f (tree b))
-> LevelOrder tree a
-> f (LevelOrder tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
levelorder a -> f b
f (tree a -> f (tree b))
-> (LevelOrder tree a -> tree a) -> LevelOrder tree a -> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. LevelOrder tree a -> tree a
forall (tree :: * -> *) a. LevelOrder tree a -> tree a
getLevelOrder
newtype RLevelOrder tree a = RLevelOrder { forall (tree :: * -> *) a. RLevelOrder tree a -> tree a
getRLevelOrder :: tree a }
deriving (forall a b. (a -> b) -> RLevelOrder tree a -> RLevelOrder tree b)
-> (forall a b. a -> RLevelOrder tree b -> RLevelOrder tree a)
-> Functor (RLevelOrder tree)
forall a b. a -> RLevelOrder tree b -> RLevelOrder tree a
forall a b. (a -> b) -> RLevelOrder tree a -> RLevelOrder tree b
forall (tree :: * -> *) a b.
Functor tree =>
a -> RLevelOrder tree b -> RLevelOrder tree a
forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> RLevelOrder tree a -> RLevelOrder tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (tree :: * -> *) a b.
Functor tree =>
(a -> b) -> RLevelOrder tree a -> RLevelOrder tree b
fmap :: forall a b. (a -> b) -> RLevelOrder tree a -> RLevelOrder tree b
$c<$ :: forall (tree :: * -> *) a b.
Functor tree =>
a -> RLevelOrder tree b -> RLevelOrder tree a
<$ :: forall a b. a -> RLevelOrder tree b -> RLevelOrder tree a
Functor
instance TreeLike tree => Foldable (RLevelOrder tree) where
foldMap :: forall m a. Monoid m => (a -> m) -> RLevelOrder tree a -> m
foldMap = (a -> m) -> RLevelOrder tree a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault
instance TreeLike tree => Traversable (RLevelOrder tree) where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RLevelOrder tree a -> f (RLevelOrder tree b)
traverse a -> f b
f = (tree b -> RLevelOrder tree b)
-> f (tree b) -> f (RLevelOrder tree b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap tree b -> RLevelOrder tree b
forall (tree :: * -> *) a. tree a -> RLevelOrder tree a
RLevelOrder (f (tree b) -> f (RLevelOrder tree b))
-> (RLevelOrder tree a -> f (tree b))
-> RLevelOrder tree a
-> f (RLevelOrder tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> tree a -> f (tree b)
forall (f :: * -> *) (tree :: * -> *) a b.
(Applicative f, TreeLike tree) =>
(a -> f b) -> tree a -> f (tree b)
rlevelorder a -> f b
f (tree a -> f (tree b))
-> (RLevelOrder tree a -> tree a)
-> RLevelOrder tree a
-> f (tree b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RLevelOrder tree a -> tree a
forall (tree :: * -> *) a. RLevelOrder tree a -> tree a
getRLevelOrder