polytree 0.0.9 → 0.0.10
raw patch · 3 files changed
+104/−81 lines, 3 files
Files
- changelog.md +5/−0
- polytree.cabal +1/−1
- src/Data/PolyTree.hs +98/−80
changelog.md view
@@ -1,3 +1,8 @@+0.0.10++* New combinators for traversing Node+* Update build+ 0.0.9 * Delete `leaves` function (use `traverse`)
polytree.cabal view
@@ -1,5 +1,5 @@ name: polytree-version: 0.0.9+version: 0.0.10 synopsis: A polymorphic rose-tree description: A rose-tree which has different data in the nodes and leaves license: BSD3
src/Data/PolyTree.hs view
@@ -59,11 +59,11 @@ type Tree' f a = Tree f a a -type Tree0 a b =+type TreeList a b = Tree [] a b -type Tree0' a =- Tree0 a a+type TreeList' a =+ TreeList a a type Tree1 a b = Tree Identity a b@@ -126,19 +126,19 @@ -- >>> Leaf "ABC" <> Leaf "DEF" :: Tree1' String -- Leaf "ABCDEF" ----- >>> Leaf "ABC" <> Node "DEF" [] :: Tree0' String+-- >>> Leaf "ABC" <> Node "DEF" [] :: TreeList' String -- Node "DEF" [] ----- >>> Leaf "ABC" <> Node "DEF" [Leaf "GHI"] :: Tree0' String+-- >>> Leaf "ABC" <> Node "DEF" [Leaf "GHI"] :: TreeList' String -- Node "DEF" [Leaf "ABCGHI"] ----- >>> Node "ABC" [] <> Leaf "DEF" :: Tree0' String+-- >>> Node "ABC" [] <> Leaf "DEF" :: TreeList' String -- Node "ABC" [] ----- >>> Node "ABC" [] <> Node "DEF" [Leaf "GHI"] :: Tree0' String+-- >>> Node "ABC" [] <> Node "DEF" [Leaf "GHI"] :: TreeList' String -- Node "ABCDEF" [] ----- >>> Node "ABC" [] <> Node "DEF" [Leaf "GHI", Node "JKL" []] :: Tree0' String+-- >>> Node "ABC" [] <> Node "DEF" [Leaf "GHI", Node "JKL" []] :: TreeList' String -- Node "ABCDEF" [] instance (Applicative f, Semigroup a, Semigroup b) => Semigroup (Tree f a b) where Leaf a1 <> Leaf a2 =@@ -155,13 +155,13 @@ -- | ----- >>> bimap (+1) (+2) (Leaf 10) :: Tree0' Int+-- >>> bimap (+1) (+2) (Leaf 10) :: TreeList' Int -- Leaf 12 ----- >>> bimap (+1) (+2) (Node 20 [Leaf 10]) :: Tree0' Int+-- >>> bimap (+1) (+2) (Node 20 [Leaf 10]) :: TreeList' Int -- Node 21 [Leaf 12] ----- >>> bimap (+1) (+2) (Node 20 [Node 30 [Leaf 10], Leaf 40]) :: Tree0' Int+-- >>> bimap (+1) (+2) (Node 20 [Node 30 [Leaf 10], Leaf 40]) :: TreeList' Int -- Node 21 [Node 31 [Leaf 12],Leaf 42] instance Functor f => Bifunctor (Tree f) where bimap _ g (Leaf b) =@@ -171,34 +171,34 @@ -- | ----- >>> fmap (+1) (Leaf 10) :: Tree0' Int+-- >>> fmap (+1) (Leaf 10) :: TreeList' Int -- Leaf 11 ----- >>> fmap (+1) (Node 20 [Leaf 10]) :: Tree0' Int+-- >>> fmap (+1) (Node 20 [Leaf 10]) :: TreeList' Int -- Node 20 [Leaf 11] ----- >>> fmap (+1) (Node 20 [Node 30 [Leaf 10], Leaf 40]) :: Tree0' Int+-- >>> fmap (+1) (Node 20 [Node 30 [Leaf 10], Leaf 40]) :: TreeList' Int -- Node 20 [Node 30 [Leaf 11],Leaf 41] instance Functor f => Functor (Tree f a) where fmap = bimap id --- >>> Leaf (+1) <.> Leaf 10 :: Tree0' Int+-- >>> Leaf (+1) <.> Leaf 10 :: TreeList' Int -- Leaf 11 ----- >>> Leaf (+1) <.> Node 10 [] :: Tree0' Int+-- >>> Leaf (+1) <.> Node 10 [] :: TreeList' Int -- Node 10 [] ----- >>> Node 20 [] <.> Node 10 [] :: Tree0' Int+-- >>> Node 20 [] <.> Node 10 [] :: TreeList' Int -- Node 20 [] ----- >>> Node 20 [] <.> Leaf 10 :: Tree0' Int+-- >>> Node 20 [] <.> Leaf 10 :: TreeList' Int -- Node 20 [] ----- >>> Leaf (+1) <.> Node 20 [Leaf 10] :: Tree0' Int+-- >>> Leaf (+1) <.> Node 20 [Leaf 10] :: TreeList' Int -- Node 20 [Leaf 11] ----- >>> Node 10 [] <.> Node 20 [Leaf 10] :: Tree0' Int+-- >>> Node 10 [] <.> Node 20 [Leaf 10] :: TreeList' Int -- Node 10 [] instance Functor f => Apply (Tree f a) where Leaf f <.> t =@@ -208,7 +208,7 @@ -- | ----- >>> pure 10 :: Tree0' Int+-- >>> pure 10 :: TreeList' Int -- Leaf 10 instance Functor f => Applicative (Tree f a) where pure =@@ -218,19 +218,19 @@ -- | ----- >>> Leaf 10 >>- \n -> Leaf (n + 1) :: Tree0' Int+-- >>> Leaf 10 >>- \n -> Leaf (n + 1) :: TreeList' Int -- Leaf 11 ----- >>> Leaf 10 >>- \n -> Node 20 [] :: Tree0' Int+-- >>> Leaf 10 >>- \n -> Node 20 [] :: TreeList' Int -- Node 20 [] ----- >>> Leaf 10 >>- \n -> Node 20 [Leaf 30] :: Tree0' Int+-- >>> Leaf 10 >>- \n -> Node 20 [Leaf 30] :: TreeList' Int -- Node 20 [Leaf 30] -- -- >>> Node 10 [] >>- Leaf -- Node 10 [] ----- >>> Node 10 [] >>- \n -> Node 20 [Leaf n] :: Tree0' Int+-- >>> Node 10 [] >>- \n -> Node 20 [Leaf n] :: TreeList' Int -- Node 10 [] instance Functor f => Bind (Tree f a) where Leaf x >>- k =@@ -260,7 +260,7 @@ -- | ----- >>> bifoldMap reverse (<> "DEF") (Leaf "ABC" :: Tree0' String)+-- >>> bifoldMap reverse (<> "DEF") (Leaf "ABC" :: TreeList' String) -- "ABCDEF" -- -- >>> bifoldMap reverse (<> "DEF") (Node "ABC" [Leaf "DEF"])@@ -360,19 +360,19 @@ -- | ----- >>> toListOf plate (Leaf 1 :: Tree0' Int)+-- >>> toListOf plate (Leaf 1 :: TreeList' Int) -- [Leaf 1] ----- >>> toListOf plate (Node 1 [] :: Tree0' Int)+-- >>> toListOf plate (Node 1 [] :: TreeList' Int) -- [] ----- >>> toListOf plate (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> toListOf plate (Node 1 [Leaf 2] :: TreeList' Int) -- [Leaf 2] ----- >>> toListOf plate (Node 1 [Leaf 2, Leaf 3, Node 4 []] :: Tree0' Int)+-- >>> toListOf plate (Node 1 [Leaf 2, Leaf 3, Node 4 []] :: TreeList' Int) -- [Leaf 2,Leaf 3,Node 4 []] ----- >>> toListOf plate (Node 1 [Leaf 2, Leaf 3, Node 4 [Leaf 5]] :: Tree0' Int)+-- >>> toListOf plate (Node 1 [Leaf 2, Leaf 3, Node 4 [Leaf 5]] :: TreeList' Int) -- [Leaf 2,Leaf 3,Node 4 [Leaf 5]] instance Traversable f => Plated (Tree f a b) where plate f (Leaf b) =@@ -453,16 +453,16 @@ -- | ----- >>> treeValue (Leaf 1 :: Tree0' Int)+-- >>> treeValue (Leaf 1 :: TreeList' Int) -- Right 1 ----- >>> treeValue (Node 1 [] :: Tree0' Int)+-- >>> treeValue (Node 1 [] :: TreeList' Int) -- Left 1 ----- >>> treeValue (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> treeValue (Node 1 [Leaf 2] :: TreeList' Int) -- Left 1 ----- >>> treeValue (Node 1 [Node 2 []] :: Tree0' Int)+-- >>> treeValue (Node 1 [Node 2 []] :: TreeList' Int) -- Left 1 treeValue :: Tree f a b@@ -472,16 +472,16 @@ -- | ----- >>> treeChildren (Leaf 1 :: Tree0' Int)+-- >>> treeChildren (Leaf 1 :: TreeList' Int) -- Left 1 ----- >>> treeChildren (Node 1 [] :: Tree0' Int)+-- >>> treeChildren (Node 1 [] :: TreeList' Int) -- Right [] ----- >>> treeChildren (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> treeChildren (Node 1 [Leaf 2] :: TreeList' Int) -- Right [Leaf 2] ----- >>> treeChildren (Node 1 [Leaf 2, Node 3 []] :: Tree0' Int)+-- >>> treeChildren (Node 1 [Leaf 2, Node 3 []] :: TreeList' Int) -- Right [Leaf 2,Node 3 []] treeChildren :: Tree f a b@@ -494,13 +494,13 @@ -- >>> toListOf nodeValue (Leaf 1) -- [] ----- >>> toListOf nodeValue (Node 1 [] :: Tree0' Int)+-- >>> toListOf nodeValue (Node 1 [] :: TreeList' Int) -- [1] ----- >>> toListOf nodeValue (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> toListOf nodeValue (Node 1 [Leaf 2] :: TreeList' Int) -- [1] ----- >>> toListOf nodeValue (Node 1 [Leaf 2, Node 3 []] :: Tree0' Int)+-- >>> toListOf nodeValue (Node 1 [Leaf 2, Node 3 []] :: TreeList' Int) -- [1] nodeValue :: Traversal'@@ -511,16 +511,16 @@ -- | ----- >>> toListOf nodeChildren (Leaf 1 :: Tree0' Int)+-- >>> toListOf nodeChildren (Leaf 1 :: TreeList' Int) -- [] ----- >>> toListOf nodeChildren (Node 1 [] :: Tree0' Int)+-- >>> toListOf nodeChildren (Node 1 [] :: TreeList' Int) -- [[]] ----- >>> toListOf nodeChildren (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> toListOf nodeChildren (Node 1 [Leaf 2] :: TreeList' Int) -- [[Leaf 2]] ----- >>> toListOf nodeChildren (Node 1 [Leaf 2, Node 3 []] :: Tree0' Int)+-- >>> toListOf nodeChildren (Node 1 [Leaf 2, Node 3 []] :: TreeList' Int) -- [[Leaf 2,Node 3 []]] nodeChildren :: Traversal@@ -609,27 +609,27 @@ -- | ----- >>> toListOf _Node0 (Leaf "ABC" :: Tree0' String)+-- >>> toListOf _Node0 (Leaf "ABC" :: TreeList' String) -- [] ----- >>> toListOf _Node0 (Node "ABC" [] :: Tree0' String)+-- >>> toListOf _Node0 (Node "ABC" [] :: TreeList' String) -- [] ----- >>> toListOf _Node0 (Node "ABC" [Leaf "DEF"] :: Tree0' String)+-- >>> toListOf _Node0 (Node "ABC" [Leaf "DEF"] :: TreeList' String) -- [("ABC",Leaf "DEF")] ----- >>> toListOf _Node0 (Node "ABC" [Leaf "DEF", Leaf "GHI"] :: Tree0' String)+-- >>> toListOf _Node0 (Node "ABC" [Leaf "DEF", Leaf "GHI"] :: TreeList' String) -- [("ABC",Leaf "DEF"),("ABC",Leaf "GHI")] ----- >>> toListOf _Node0 (Node "ABC" [Leaf "DEF", Node "GHI" []] :: Tree0' String)+-- >>> toListOf _Node0 (Node "ABC" [Leaf "DEF", Node "GHI" []] :: TreeList' String) -- [("ABC",Leaf "DEF"),("ABC",Node "GHI" [])] _Node0 :: Monoid a' => Traversal- (Tree0 a b)- (Tree0 a' b)- (a, Tree0 a b)- (a', Tree0 a' b)+ (TreeList a b)+ (TreeList a' b)+ (a, TreeList a b)+ (a', TreeList a' b) _Node0 _ (Leaf b) = pure (Leaf b) _Node0 f (Node a t) =@@ -672,11 +672,11 @@ node = Node -node0 ::+nodeList :: a- -> [Tree0 a b]- -> Tree0 a b-node0 =+ -> [TreeList a b]+ -> TreeList a b+nodeList = Node node1 ::@@ -688,16 +688,16 @@ -- | ----- >>> traverseNode (\(a, t) -> [(a, t)]) (Leaf 1 :: Tree0' Int)+-- >>> traverseNode (\(a, t) -> [(a, t)]) (Leaf 1 :: TreeList' Int) -- [Leaf 1] ----- >>> traverseNode (\(a, t) -> [(a, t)]) (Node 1 [] :: Tree0' Int)+-- >>> traverseNode (\(a, t) -> [(a, t)]) (Node 1 [] :: TreeList' Int) -- [Node (1,[]) []] ----- >>> traverseNode (\(a, t) -> [(a, t)]) (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> traverseNode (\(a, t) -> [(a, t)]) (Node 1 [Leaf 2] :: TreeList' Int) -- [Node (1,[Leaf 2]) [Leaf 2]] ----- >>> traverseNode (\(a, t) -> [(a, t)]) (Node 1 [Leaf 2, Node 3 []] :: Tree0' Int)+-- >>> traverseNode (\(a, t) -> [(a, t)]) (Node 1 [Leaf 2, Node 3 []] :: TreeList' Int) -- [Node (1,[Leaf 2,Node 3 []]) [Leaf 2,Node (3,[]) []]] traverseNode :: Traversable f =>@@ -715,18 +715,36 @@ traverseNode_ f (Node a t) = f (a, t) *> traverse_ (traverseNode_ f) t +traverseNodeValues ::+ Traversable f =>+ Traversal (Tree f a x) (Tree f b x) a b+traverseNodeValues _ (Leaf b) =+ pure (Leaf b)+traverseNodeValues f (Node a t) =+ Node <$> f a <*> traverse (traverseNodeValues f) t++mapNodeValues ::+ Functor f =>+ (a -> b)+ -> Tree f a x+ -> Tree f b x+mapNodeValues _ (Leaf b) =+ Leaf b+mapNodeValues f (Node a t) =+ Node (f a) (fmap (mapNodeValues f) t)+ -- | ----- >>> view treeIso (Leaf 1 :: Tree0' Int)+-- >>> view treeIso (Leaf 1 :: TreeList' Int) -- (1,Nothing) ----- >>> view treeIso (Node 1 [] :: Tree0' Int)+-- >>> view treeIso (Node 1 [] :: TreeList' Int) -- (1,Just []) ----- >>> view treeIso (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> view treeIso (Node 1 [Leaf 2] :: TreeList' Int) -- (1,Just [Leaf 2]) ----- >>> view treeIso (Node 1 [Leaf 2, Node 3 []] :: Tree0' Int)+-- >>> view treeIso (Node 1 [Leaf 2, Node 3 []] :: TreeList' Int) -- (1,Just [Leaf 2,Node 3 []]) treeIso :: Iso@@ -741,16 +759,16 @@ -- | ----- >>> view treeValue' (Leaf 1 :: Tree0' Int)+-- >>> view treeValue' (Leaf 1 :: TreeList' Int) -- 1 ----- >>> view treeValue' (Node 1 [] :: Tree0' Int)+-- >>> view treeValue' (Node 1 [] :: TreeList' Int) -- 1 ----- >>> view treeValue' (Node 1 [Leaf 2] :: Tree0' Int)+-- >>> view treeValue' (Node 1 [Leaf 2] :: TreeList' Int) -- 1 ----- >>> view treeValue' (Node 1 [Leaf 2, Node 3 []] :: Tree0' Int)+-- >>> view treeValue' (Node 1 [Leaf 2, Node 3 []] :: TreeList' Int) -- 1 treeValue' :: Lens'@@ -761,19 +779,19 @@ -- | ----- >>> view treeChildren' (Leaf 1 :: Tree0' Int)+-- >>> view treeChildren' (Leaf 1 :: TreeList' Int) -- Nothing ----- >>> view treeChildren' (Node 1 [] :: Tree0' Int)+-- >>> view treeChildren' (Node 1 [] :: TreeList' Int) -- Just [] ----- >>> view treeChildren' (Node 1 [Leaf 2, Leaf 3] :: Tree0' Int)+-- >>> view treeChildren' (Node 1 [Leaf 2, Leaf 3] :: TreeList' Int) -- Just [Leaf 2,Leaf 3] ----- >>> view treeChildren' (Node 1 [Leaf 2, Leaf 3, Node 4 []] :: Tree0' Int)+-- >>> view treeChildren' (Node 1 [Leaf 2, Leaf 3, Node 4 []] :: TreeList' Int) -- Just [Leaf 2,Leaf 3,Node 4 []] ----- >>> view treeChildren' (Node 1 [Leaf 2, Leaf 3, Node 4 [Node 5 []]] :: Tree0' Int)+-- >>> view treeChildren' (Node 1 [Leaf 2, Leaf 3, Node 4 [Node 5 []]] :: TreeList' Int) -- Just [Leaf 2,Leaf 3,Node 4 [Node 5 []]] treeChildren' :: Lens@@ -840,8 +858,8 @@ -- Node 1 [Node 2 []] baseTree :: Iso- (Tree0 a Void)- (Tree0 a' Void)+ (TreeList a Void)+ (TreeList a' Void) (Tree.Tree a) (Tree.Tree a') baseTree =@@ -851,7 +869,7 @@ go (Leaf b) = absurd b in Tree.Node h (fmap go c)- mkTree0 (Tree.Node h t) = Node h (fmap mkTree0 t)+ mkTreeList (Tree.Node h t) = Node h (fmap mkTreeList t) in iso (matchTree absurd mkTree)- (\(Tree.Node h t) -> Node h (fmap mkTree0 t))+ (\(Tree.Node h t) -> Node h (fmap mkTreeList t))