-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Please see the README on Github at -- https://github.com/oisdk/binary-tree#readme @package binary-tree @version 0.1.0.0 -- |

WARNING

-- -- This module is considered internal. -- -- The Package Versioning Policy does not apply. -- -- This contents of this module may change in any way whatsoever -- and without any warning between minor versions of this package. -- -- Authors importing this module are expected to track development -- closely. -- --

Description

-- -- This module exports some utility functions common to both tree -- modules. module Data.Tree.Binary.Internal -- | An abstract representation of a textual drawing of a tree. data Drawing Nil :: Drawing NewLine :: !Drawing -> Drawing BottomLeft :: !Drawing -> Drawing BottomRight :: !Drawing -> Drawing TopLeft :: !Drawing -> Drawing TopRight :: !Drawing -> Drawing Vert :: !Drawing -> Drawing Split :: !Drawing -> Drawing Item :: !String -> Drawing -> Drawing Padding :: {-# UNPACK #-} !Int -> !Drawing -> Drawing -- | Convert a tree to the Drawing type. This function is exposed so that -- users may replace the call to runDrawing in drawTree -- with a more efficient implementation that could use (for example) -- Text. toDrawing :: (a -> String) -> (t -> Maybe (a, t, t)) -> t -> Drawing -- | A function to convert a drawing to a string. runDrawing :: Drawing -> ShowS -- | Given an uncons function for a binary tree, draw the tree in a -- structured, human-readable way. drawTree :: (a -> String) -> (t -> Maybe (a, t, t)) -> t -> ShowS -- | A clone of Control.Monad.State.Strict, reimplemented here to avoid the -- dependency. newtype State s a State :: (s -> (a, s)) -> State s a [runState] :: State s a -> s -> (a, s) -- | Evaluate a stateful action. evalState :: State s a -> s -> a -- | Identity functor and monad. (a non-strict monad) newtype Identity a :: * -> * Identity :: a -> Identity a [runIdentity] :: Identity a -> a instance GHC.Base.Functor (Data.Tree.Binary.Internal.State s) instance GHC.Base.Applicative (Data.Tree.Binary.Internal.State s) -- | This module provides a simple inorder binary tree, as is needed in -- several applications. Instances, if sensible, are defined, and -- generally effort is made to keep the implementation as generic as -- possible. module Data.Tree.Binary.Inorder -- | An inorder binary tree. data Tree a Leaf :: Tree a Node :: (Tree a) -> a -> (Tree a) -> Tree a -- | Unfold a tree from a seed. unfoldTree :: (b -> Maybe (b, a, b)) -> b -> Tree a -- | replicate n a creates a tree of size n filled -- a. -- -- 
--   >>> putStr (drawTree (replicate 4 ()))
--        ┌()
--     ┌()┘
--   ()┤
--     └()
--
-- -- 
--   \(NonNegative n) -> length (replicate n ()) === n
--
replicate :: Int -> a -> Tree a -- | replicateA n a replicates the action a -- n times, trying to balance the result as much as possible. -- The actions are executed in a preorder traversal (same as the -- Foldable instance.) -- -- 
--   >>> toList (evalState (replicateA 10 (State (\s -> (s, s + 1)))) 1)
--   [1,2,3,4,5,6,7,8,9,10]
--
replicateA :: Applicative f => Int -> f a -> f (Tree a) -- | A binary tree with one element. singleton :: a -> Tree a -- | A binary tree with no elements. empty :: Tree a -- | Construct a tree from a list, in an inorder fashion. -- -- 
--   toList (fromList xs) === xs
--
fromList :: [a] -> Tree a -- | Fold over a tree. -- -- 
--   foldTree Leaf Node xs === xs
--
foldTree :: b -> (b -> a -> b -> b) -> Tree a -> b -- | The depth of the tree. -- -- 
--   >>> depth empty
--   0
--
-- -- 
--   >>> depth (singleton ())
--   1
--
depth :: Tree a -> Int -- | Convert a tree to a human-readable structural representation. -- -- 
--   >>> putStr (drawTree (fromList [1..7]))
--      ┌1
--    ┌2┤
--    │ └3
--   4┤
--    │ ┌5
--    └6┤
--      └7
--
drawTree :: Show a => Tree a -> String -- | Pretty-print a tree with a custom show function. -- -- 
--   >>> putStr (drawTreeWith (const "─") (fromList [1..7]) "")
--      ┌─
--    ┌─┤
--    │ └─
--   ─┤
--    │ ┌─
--    └─┤
--      └─
--
-- -- 
--   >>> putStr (drawTreeWith id (singleton "abc") "")
--   abc
--
-- -- 
--   >>> putStr (drawTreeWith id (Node (singleton "d") "abc" Leaf) "")
--      ┌d
--   abc┘
--
-- -- 
--   >>> putStr (drawTreeWith id (fromList ["abc", "d", "ef", "ghij"]) "")
--       ┌abc
--     ┌d┘
--   ef┤
--     └ghij
--
drawTreeWith :: (a -> String) -> Tree a -> ShowS -- | Pretty-print a tree. -- -- 
--   >>> printTree (fromList [1..7])
--      ┌1
--    ┌2┤
--    │ └3
--   4┤
--    │ ┌5
--    └6┤
--      └7
--
-- -- 
--   >>> printTree (singleton 1)
--   1
--
-- -- 
--   >>> printTree (singleton 1 `mappend` singleton 2)
--   1┐
--    └2
--
printTree :: Show a => Tree a -> IO () instance GHC.Generics.Generic1 Data.Tree.Binary.Inorder.Tree instance GHC.Generics.Generic (Data.Tree.Binary.Inorder.Tree a) instance Data.Data.Data a => Data.Data.Data (Data.Tree.Binary.Inorder.Tree a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Tree.Binary.Inorder.Tree a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Tree.Binary.Inorder.Tree a) instance GHC.Read.Read a => GHC.Read.Read (Data.Tree.Binary.Inorder.Tree a) instance GHC.Show.Show a => GHC.Show.Show (Data.Tree.Binary.Inorder.Tree a) instance GHC.Base.Functor Data.Tree.Binary.Inorder.Tree instance GHC.Base.Applicative Data.Tree.Binary.Inorder.Tree instance GHC.Base.Alternative Data.Tree.Binary.Inorder.Tree instance Data.Foldable.Foldable Data.Tree.Binary.Inorder.Tree instance Data.Traversable.Traversable Data.Tree.Binary.Inorder.Tree instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Tree.Binary.Inorder.Tree a) instance Data.Functor.Classes.Eq1 Data.Tree.Binary.Inorder.Tree instance Data.Functor.Classes.Ord1 Data.Tree.Binary.Inorder.Tree instance Data.Functor.Classes.Show1 Data.Tree.Binary.Inorder.Tree instance Data.Functor.Classes.Read1 Data.Tree.Binary.Inorder.Tree instance Data.Semigroup.Semigroup (Data.Tree.Binary.Inorder.Tree a) instance GHC.Base.Monoid (Data.Tree.Binary.Inorder.Tree a) -- | This module provides a simple leafy binary tree, as is needed in -- several applications. Instances, if sensible, are defined, and -- generally effort is made to keep the implementation as generic as -- possible. module Data.Tree.Binary.Leafy -- | A leafy binary tree. data Tree a Leaf :: a -> Tree a (:*:) :: Tree a -> Tree a -> Tree a -- | Unfold a tree from a seed. unfoldTree :: (b -> Either a (b, b)) -> b -> Tree a -- | replicate n a creates a tree of size n filled -- with a. -- -- 
--   >>> printTree (replicate 4 ())
--    ┌()
--   ┌┤
--   │└()
--   ┤
--   │┌()
--   └┤
--    └()
--
-- -- 
--   \(Positive n) -> length (replicate n ()) === n
--
replicate :: Int -> a -> Tree a -- | replicateA n a replicates the action a -- n times, trying to balance the result as much as possible. -- The actions are executed in the same order as the Foldable -- instance. -- -- 
--   >>> toList (evalState (replicateA 10 (State (\s -> (s, s + 1)))) 1)
--   [1,2,3,4,5,6,7,8,9,10]
--
replicateA :: Applicative f => Int -> f a -> f (Tree a) -- | A binary tree with one element. singleton :: a -> Tree a -- | Construct a tree from a list. -- -- The constructed tree is somewhat, but not totally, balanced. -- -- 
--   >>> printTree (fromList [1,2,3,4])
--    ┌1
--   ┌┤
--   │└2
--   ┤
--   │┌3
--   └┤
--    └4
--
-- -- 
--   >>> printTree (fromList [1,2,3,4,5,6])
--     ┌1
--    ┌┤
--    │└2
--   ┌┤
--   ││┌3
--   │└┤
--   │ └4
--   ┤
--   │┌5
--   └┤
--    └6
--
fromList :: HasCallStack => [a] -> Tree a -- | Fold over a tree. -- -- 
--   foldTree Leaf (:*:) xs === xs
--
foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b -- | The depth of the tree. -- -- 
--   >>> depth (singleton ())
--   1
--
depth :: Tree a -> Int -- | Convert a tree to a human-readable structural representation. -- -- 
--   >>> putStr (drawTree (Leaf 1 :*: Leaf 2 :*: Leaf 3))
--    ┌1
--   ┌┤
--   │└2
--   ┤
--   └3
--
drawTree :: Show a => Tree a -> String -- | Pretty-print a tree with a custom show function. drawTreeWith :: (a -> String) -> Tree a -> ShowS -- | Pretty-print a tree printTree :: Show a => Tree a -> IO () instance GHC.Generics.Generic1 Data.Tree.Binary.Leafy.Tree instance GHC.Generics.Generic (Data.Tree.Binary.Leafy.Tree a) instance Data.Data.Data a => Data.Data.Data (Data.Tree.Binary.Leafy.Tree a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Tree.Binary.Leafy.Tree a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Tree.Binary.Leafy.Tree a) instance GHC.Read.Read a => GHC.Read.Read (Data.Tree.Binary.Leafy.Tree a) instance GHC.Show.Show a => GHC.Show.Show (Data.Tree.Binary.Leafy.Tree a) instance GHC.Base.Functor Data.Tree.Binary.Leafy.Tree instance GHC.Base.Applicative Data.Tree.Binary.Leafy.Tree instance GHC.Base.Monad Data.Tree.Binary.Leafy.Tree instance Control.Monad.Fix.MonadFix Data.Tree.Binary.Leafy.Tree instance Control.Monad.Zip.MonadZip Data.Tree.Binary.Leafy.Tree instance Data.Semigroup.Semigroup (Data.Tree.Binary.Leafy.Tree a) instance Data.Foldable.Foldable Data.Tree.Binary.Leafy.Tree instance Data.Traversable.Traversable Data.Tree.Binary.Leafy.Tree instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Tree.Binary.Leafy.Tree a) instance Data.Functor.Classes.Eq1 Data.Tree.Binary.Leafy.Tree instance Data.Functor.Classes.Ord1 Data.Tree.Binary.Leafy.Tree instance Data.Functor.Classes.Show1 Data.Tree.Binary.Leafy.Tree instance Data.Functor.Classes.Read1 Data.Tree.Binary.Leafy.Tree -- | This module provides a simple preorder binary tree, as is needed in -- several applications. Instances, if sensible, are defined, and -- generally effort is made to keep the implementation as generic as -- possible. module Data.Tree.Binary.Preorder -- | A preorder binary tree. data Tree a Leaf :: Tree a Node :: a -> (Tree a) -> (Tree a) -> Tree a -- | Unfold a tree from a seed. unfoldTree :: (b -> Maybe (a, b, b)) -> b -> Tree a -- | replicate n a creates a tree of size n filled -- a. -- -- 
--   >>> putStr (drawTree (replicate 4 ()))
--        ┌()
--     ┌()┘
--   ()┤
--     └()
--
-- -- 
--   \(NonNegative n) -> length (replicate n ()) === n
--
replicate :: Int -> a -> Tree a -- | replicateA n a replicates the action a -- n times, trying to balance the result as much as possible. -- The actions are executed in a preorder traversal (same as the -- Foldable instance.) -- -- 
--   >>> toList (evalState (replicateA 10 (State (\s -> (s, s + 1)))) 1)
--   [1,2,3,4,5,6,7,8,9,10]
--
replicateA :: Applicative f => Int -> f a -> f (Tree a) -- | A binary tree with one element. singleton :: a -> Tree a -- | A binary tree with no elements. empty :: Tree a -- | Construct a tree from a list, in an preorder fashion. -- -- 
--   toList (fromList xs) === xs
--
fromList :: [a] -> Tree a -- | Fold over a tree. -- -- 
--   foldTree Leaf Node xs === xs
--
foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b -- | The depth of the tree. -- -- 
--   >>> depth empty
--   0
--
-- -- 
--   >>> depth (singleton ())
--   1
--
depth :: Tree a -> Int -- | Convert a tree to a human-readable structural representation. -- -- 
--   >>> putStr (drawTree (fromList [1..7]))
--      ┌3
--    ┌2┤
--    │ └4
--   1┤
--    │ ┌6
--    └5┤
--      └7
--
drawTree :: Show a => Tree a -> String -- | Pretty-print a tree with a custom show function. -- -- 
--   >>> putStr (drawTreeWith (const "─") (fromList [1..7]) "")
--      ┌─
--    ┌─┤
--    │ └─
--   ─┤
--    │ ┌─
--    └─┤
--      └─
--
-- -- 
--   >>> putStr (drawTreeWith id (singleton "abc") "")
--   abc
--
-- -- 
--   >>> putStr (drawTreeWith id (Node "abc" (singleton  "d") Leaf) "")
--      ┌d
--   abc┘
--
-- -- 
--   >>> putStr (drawTreeWith id (fromList ["abc", "d", "ef", "ghij"]) "")
--        ┌ef
--      ┌d┘
--   abc┤
--      └ghij
--
drawTreeWith :: (a -> String) -> Tree a -> ShowS -- | Pretty-print a tree. -- -- 
--   >>> printTree (fromList [1..7])
--      ┌3
--    ┌2┤
--    │ └4
--   1┤
--    │ ┌6
--    └5┤
--      └7
--
-- -- 
--   >>> printTree (singleton 1 `mappend` singleton 2)
--   1┐
--    └2
--
printTree :: Show a => Tree a -> IO () instance GHC.Generics.Generic1 Data.Tree.Binary.Preorder.Tree instance GHC.Generics.Generic (Data.Tree.Binary.Preorder.Tree a) instance Data.Data.Data a => Data.Data.Data (Data.Tree.Binary.Preorder.Tree a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Tree.Binary.Preorder.Tree a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Tree.Binary.Preorder.Tree a) instance GHC.Read.Read a => GHC.Read.Read (Data.Tree.Binary.Preorder.Tree a) instance GHC.Show.Show a => GHC.Show.Show (Data.Tree.Binary.Preorder.Tree a) instance GHC.Base.Functor Data.Tree.Binary.Preorder.Tree instance GHC.Base.Applicative Data.Tree.Binary.Preorder.Tree instance GHC.Base.Alternative Data.Tree.Binary.Preorder.Tree instance Data.Foldable.Foldable Data.Tree.Binary.Preorder.Tree instance Data.Traversable.Traversable Data.Tree.Binary.Preorder.Tree instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Tree.Binary.Preorder.Tree a) instance Data.Functor.Classes.Eq1 Data.Tree.Binary.Preorder.Tree instance Data.Functor.Classes.Ord1 Data.Tree.Binary.Preorder.Tree instance Data.Functor.Classes.Show1 Data.Tree.Binary.Preorder.Tree instance Data.Functor.Classes.Read1 Data.Tree.Binary.Preorder.Tree instance Data.Semigroup.Semigroup (Data.Tree.Binary.Preorder.Tree a) instance GHC.Base.Monoid (Data.Tree.Binary.Preorder.Tree a)