Safe Haskell	None
Language	Haskell2010

Data.BinaryTree

Contents

Converting into a Data.Tree
Internal Node Tree

Synopsis

Documentation

data BinLeafTree v a Source #

Constructors

Leaf !a
Node (BinLeafTree v a) !v (BinLeafTree v a)

Instances

Measured v a => Measured v (BinLeafTree v a) Source #
Methods measure :: BinLeafTree v a -> v Source #
Functor (BinLeafTree v) Source #
Methods fmap :: (a -> b) -> BinLeafTree v a -> BinLeafTree v b # (<$) :: a -> BinLeafTree v b -> BinLeafTree v a #
Foldable (BinLeafTree v) Source #
Methods fold :: Monoid m => BinLeafTree v m -> m # foldMap :: Monoid m => (a -> m) -> BinLeafTree v a -> m # foldr :: (a -> b -> b) -> b -> BinLeafTree v a -> b # foldr' :: (a -> b -> b) -> b -> BinLeafTree v a -> b # foldl :: (b -> a -> b) -> b -> BinLeafTree v a -> b # foldl' :: (b -> a -> b) -> b -> BinLeafTree v a -> b # foldr1 :: (a -> a -> a) -> BinLeafTree v a -> a # foldl1 :: (a -> a -> a) -> BinLeafTree v a -> a # toList :: BinLeafTree v a -> [a] # null :: BinLeafTree v a -> Bool # length :: BinLeafTree v a -> Int # elem :: Eq a => a -> BinLeafTree v a -> Bool # maximum :: Ord a => BinLeafTree v a -> a # minimum :: Ord a => BinLeafTree v a -> a # sum :: Num a => BinLeafTree v a -> a # product :: Num a => BinLeafTree v a -> a #
Traversable (BinLeafTree v) Source #
Methods traverse :: Applicative f => (a -> f b) -> BinLeafTree v a -> f (BinLeafTree v b) # sequenceA :: Applicative f => BinLeafTree v (f a) -> f (BinLeafTree v a) # mapM :: Monad m => (a -> m b) -> BinLeafTree v a -> m (BinLeafTree v b) # sequence :: Monad m => BinLeafTree v (m a) -> m (BinLeafTree v a) #
Foldable1 (BinLeafTree v) Source #
Methods fold1 :: Semigroup m => BinLeafTree v m -> m # foldMap1 :: Semigroup m => (a -> m) -> BinLeafTree v a -> m #
(Eq v, Eq a) => Eq (BinLeafTree v a) Source #
Methods (==) :: BinLeafTree v a -> BinLeafTree v a -> Bool # (/=) :: BinLeafTree v a -> BinLeafTree v a -> Bool #
(Ord v, Ord a) => Ord (BinLeafTree v a) Source #
Methods compare :: BinLeafTree v a -> BinLeafTree v a -> Ordering # (<) :: BinLeafTree v a -> BinLeafTree v a -> Bool # (<=) :: BinLeafTree v a -> BinLeafTree v a -> Bool # (>) :: BinLeafTree v a -> BinLeafTree v a -> Bool # (>=) :: BinLeafTree v a -> BinLeafTree v a -> Bool # max :: BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a # min :: BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a #
(Read v, Read a) => Read (BinLeafTree v a) Source #
Methods readsPrec :: Int -> ReadS (BinLeafTree v a) # readList :: ReadS [BinLeafTree v a] # readPrec :: ReadPrec (BinLeafTree v a) # readListPrec :: ReadPrec [BinLeafTree v a] #
(Show v, Show a) => Show (BinLeafTree v a) Source #
Methods showsPrec :: Int -> BinLeafTree v a -> ShowS # show :: BinLeafTree v a -> String # showList :: [BinLeafTree v a] -> ShowS #
Generic (BinLeafTree v a) Source #
Associated Types type Rep (BinLeafTree v a) :: * -> * # Methods from :: BinLeafTree v a -> Rep (BinLeafTree v a) x # to :: Rep (BinLeafTree v a) x -> BinLeafTree v a #
Measured v a => Semigroup (BinLeafTree v a) Source #
Methods (<>) :: BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a # sconcat :: NonEmpty (BinLeafTree v a) -> BinLeafTree v a # stimes :: Integral b => b -> BinLeafTree v a -> BinLeafTree v a #
(NFData v, NFData a) => NFData (BinLeafTree v a) Source #
Methods rnf :: BinLeafTree v a -> () #
type Rep (BinLeafTree v a) Source #
type Rep (BinLeafTree v a) = D1 (MetaData "BinLeafTree" "Data.BinaryTree" "hgeometry-0.6.0.0-ODn7ZyBfwj6IkLPAAzetJ" False) ((:+:) (C1 (MetaCons "Leaf" PrefixI False) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a))) (C1 (MetaCons "Node" PrefixI False) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinLeafTree v a))) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 v)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinLeafTree v a)))))))

class Semigroup v => Measured v a | a -> v where Source #

Minimal complete definition

measure

Methods

measure :: a -> v Source #

Instances

Measured Size (Elem a) Source #
Methods measure :: Elem a -> Size Source #
Measured v a => Measured v (BinLeafTree v a) Source #
Methods measure :: BinLeafTree v a -> v Source #
Semigroup v => Measured v (NodeData d r v) Source #
Methods measure :: NodeData d r v -> v Source #
Measured [I a] (I a) Source #
Methods measure :: I a -> [I a] Source #

node :: Measured v a => BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a Source #

smart constructor

asBalancedBinLeafTree :: NonEmpty a -> BinLeafTree Size (Elem a) Source #

Create a balanced tree, i.e. a tree of height $O(\log n)$ with the elements in the leaves.

$O(n)$ time.

foldUp :: (b -> v -> b -> b) -> (a -> b) -> BinLeafTree v a -> b Source #

Given a function to combine internal nodes into b's and leafs into b's, traverse the tree bottom up, and combine everything into one b.

foldUpData :: (w -> v -> w -> w) -> (a -> w) -> BinLeafTree v a -> BinLeafTree w a Source #

Traverses the tree bottom up, recomputing the assocated values.

zipExactWith :: (u -> v -> w) -> (a -> b -> c) -> BinLeafTree u a -> BinLeafTree v b -> BinLeafTree w c Source #

Takes two trees, that have the same structure, and uses the provided functions to "zip" them together

newtype Size Source #

Constructors

Size Int

Instances

Enum Size Source #
Methods succ :: Size -> Size # pred :: Size -> Size # toEnum :: Int -> Size # fromEnum :: Size -> Int # enumFrom :: Size -> [Size] # enumFromThen :: Size -> Size -> [Size] # enumFromTo :: Size -> Size -> [Size] # enumFromThenTo :: Size -> Size -> Size -> [Size] #
Eq Size Source #
Methods (==) :: Size -> Size -> Bool # (/=) :: Size -> Size -> Bool #
Integral Size Source #
Methods quot :: Size -> Size -> Size # rem :: Size -> Size -> Size # div :: Size -> Size -> Size # mod :: Size -> Size -> Size # quotRem :: Size -> Size -> (Size, Size) # divMod :: Size -> Size -> (Size, Size) # toInteger :: Size -> Integer #
Num Size Source #
Methods (+) :: Size -> Size -> Size # (-) :: Size -> Size -> Size # (*) :: Size -> Size -> Size # negate :: Size -> Size # abs :: Size -> Size # signum :: Size -> Size # fromInteger :: Integer -> Size #
Ord Size Source #
Methods compare :: Size -> Size -> Ordering # (<) :: Size -> Size -> Bool # (<=) :: Size -> Size -> Bool # (>) :: Size -> Size -> Bool # (>=) :: Size -> Size -> Bool # max :: Size -> Size -> Size # min :: Size -> Size -> Size #
Read Size Source #
Methods readsPrec :: Int -> ReadS Size # readList :: ReadS [Size] # readPrec :: ReadPrec Size # readListPrec :: ReadPrec [Size] #
Real Size Source #
Methods toRational :: Size -> Rational #
Show Size Source #
Methods showsPrec :: Int -> Size -> ShowS # show :: Size -> String # showList :: [Size] -> ShowS #
Generic Size Source #
Associated Types type Rep Size :: * -> * # Methods from :: Size -> Rep Size x # to :: Rep Size x -> Size #
Semigroup Size Source #
Methods (<>) :: Size -> Size -> Size # sconcat :: NonEmpty Size -> Size # stimes :: Integral b => b -> Size -> Size #
Monoid Size Source #
Methods mempty :: Size # mappend :: Size -> Size -> Size # mconcat :: [Size] -> Size #
NFData Size Source #
Methods rnf :: Size -> () #
Measured Size (Elem a) Source #
Methods measure :: Elem a -> Size Source #
type Rep Size Source #
type Rep Size = D1 (MetaData "Size" "Data.BinaryTree" "hgeometry-0.6.0.0-ODn7ZyBfwj6IkLPAAzetJ" True) (C1 (MetaCons "Size" PrefixI False) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int)))

newtype Elem a Source #

Constructors

Elem
Fields _unElem :: a

Instances

Functor Elem Source #
Methods fmap :: (a -> b) -> Elem a -> Elem b # (<$) :: a -> Elem b -> Elem a #
Foldable Elem Source #
Methods fold :: Monoid m => Elem m -> m # foldMap :: Monoid m => (a -> m) -> Elem a -> m # foldr :: (a -> b -> b) -> b -> Elem a -> b # foldr' :: (a -> b -> b) -> b -> Elem a -> b # foldl :: (b -> a -> b) -> b -> Elem a -> b # foldl' :: (b -> a -> b) -> b -> Elem a -> b # foldr1 :: (a -> a -> a) -> Elem a -> a # foldl1 :: (a -> a -> a) -> Elem a -> a # toList :: Elem a -> [a] # null :: Elem a -> Bool # length :: Elem a -> Int # elem :: Eq a => a -> Elem a -> Bool # maximum :: Ord a => Elem a -> a # minimum :: Ord a => Elem a -> a # sum :: Num a => Elem a -> a # product :: Num a => Elem a -> a #
Traversable Elem Source #
Methods traverse :: Applicative f => (a -> f b) -> Elem a -> f (Elem b) # sequenceA :: Applicative f => Elem (f a) -> f (Elem a) # mapM :: Monad m => (a -> m b) -> Elem a -> m (Elem b) # sequence :: Monad m => Elem (m a) -> m (Elem a) #
Measured Size (Elem a) Source #
Methods measure :: Elem a -> Size Source #
Eq a => Eq (Elem a) Source #
Methods (==) :: Elem a -> Elem a -> Bool # (/=) :: Elem a -> Elem a -> Bool #
Ord a => Ord (Elem a) Source #
Methods compare :: Elem a -> Elem a -> Ordering # (<) :: Elem a -> Elem a -> Bool # (<=) :: Elem a -> Elem a -> Bool # (>) :: Elem a -> Elem a -> Bool # (>=) :: Elem a -> Elem a -> Bool # max :: Elem a -> Elem a -> Elem a # min :: Elem a -> Elem a -> Elem a #
Read a => Read (Elem a) Source #
Methods readsPrec :: Int -> ReadS (Elem a) # readList :: ReadS [Elem a] # readPrec :: ReadPrec (Elem a) # readListPrec :: ReadPrec [Elem a] #
Show a => Show (Elem a) Source #
Methods showsPrec :: Int -> Elem a -> ShowS # show :: Elem a -> String # showList :: [Elem a] -> ShowS #

data Sized a Source #

Constructors

Sized !Size a

Instances

Functor Sized Source #
Methods fmap :: (a -> b) -> Sized a -> Sized b # (<$) :: a -> Sized b -> Sized a #
Foldable Sized Source #
Methods fold :: Monoid m => Sized m -> m # foldMap :: Monoid m => (a -> m) -> Sized a -> m # foldr :: (a -> b -> b) -> b -> Sized a -> b # foldr' :: (a -> b -> b) -> b -> Sized a -> b # foldl :: (b -> a -> b) -> b -> Sized a -> b # foldl' :: (b -> a -> b) -> b -> Sized a -> b # foldr1 :: (a -> a -> a) -> Sized a -> a # foldl1 :: (a -> a -> a) -> Sized a -> a # toList :: Sized a -> [a] # null :: Sized a -> Bool # length :: Sized a -> Int # elem :: Eq a => a -> Sized a -> Bool # maximum :: Ord a => Sized a -> a # minimum :: Ord a => Sized a -> a # sum :: Num a => Sized a -> a # product :: Num a => Sized a -> a #
Traversable Sized Source #
Methods traverse :: Applicative f => (a -> f b) -> Sized a -> f (Sized b) # sequenceA :: Applicative f => Sized (f a) -> f (Sized a) # mapM :: Monad m => (a -> m b) -> Sized a -> m (Sized b) # sequence :: Monad m => Sized (m a) -> m (Sized a) #
Eq a => Eq (Sized a) Source #
Methods (==) :: Sized a -> Sized a -> Bool # (/=) :: Sized a -> Sized a -> Bool #
Ord a => Ord (Sized a) Source #
Methods compare :: Sized a -> Sized a -> Ordering # (<) :: Sized a -> Sized a -> Bool # (<=) :: Sized a -> Sized a -> Bool # (>) :: Sized a -> Sized a -> Bool # (>=) :: Sized a -> Sized a -> Bool # max :: Sized a -> Sized a -> Sized a # min :: Sized a -> Sized a -> Sized a #
Show a => Show (Sized a) Source #
Methods showsPrec :: Int -> Sized a -> ShowS # show :: Sized a -> String # showList :: [Sized a] -> ShowS #
Generic (Sized a) Source #
Associated Types type Rep (Sized a) :: * -> * # Methods from :: Sized a -> Rep (Sized a) x # to :: Rep (Sized a) x -> Sized a #
Semigroup a => Semigroup (Sized a) Source #
Methods (<>) :: Sized a -> Sized a -> Sized a # sconcat :: NonEmpty (Sized a) -> Sized a # stimes :: Integral b => b -> Sized a -> Sized a #
Monoid a => Monoid (Sized a) Source #
Methods mempty :: Sized a # mappend :: Sized a -> Sized a -> Sized a # mconcat :: [Sized a] -> Sized a #
NFData a => NFData (Sized a) Source #
Methods rnf :: Sized a -> () #
type Rep (Sized a) Source #
type Rep (Sized a) = D1 (MetaData "Sized" "Data.BinaryTree" "hgeometry-0.6.0.0-ODn7ZyBfwj6IkLPAAzetJ" False) (C1 (MetaCons "Sized" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Size)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a))))

Converting into a Data.Tree

data RoseElem v a Source #

Constructors

InternalNode v
LeafNode a

Instances

Functor (RoseElem v) Source #
Methods fmap :: (a -> b) -> RoseElem v a -> RoseElem v b # (<$) :: a -> RoseElem v b -> RoseElem v a #
(Eq a, Eq v) => Eq (RoseElem v a) Source #
Methods (==) :: RoseElem v a -> RoseElem v a -> Bool # (/=) :: RoseElem v a -> RoseElem v a -> Bool #
(Show a, Show v) => Show (RoseElem v a) Source #
Methods showsPrec :: Int -> RoseElem v a -> ShowS # show :: RoseElem v a -> String # showList :: [RoseElem v a] -> ShowS #

toRoseTree :: BinLeafTree v a -> Tree (RoseElem v a) Source #

drawTree :: (Show v, Show a) => BinLeafTree v a -> String Source #

Internal Node Tree

data BinaryTree a Source #

Constructors

Nil
Internal (BinaryTree a) !a (BinaryTree a)

Instances

Functor BinaryTree Source #
Methods fmap :: (a -> b) -> BinaryTree a -> BinaryTree b # (<$) :: a -> BinaryTree b -> BinaryTree a #
Foldable BinaryTree Source #
Methods fold :: Monoid m => BinaryTree m -> m # foldMap :: Monoid m => (a -> m) -> BinaryTree a -> m # foldr :: (a -> b -> b) -> b -> BinaryTree a -> b # foldr' :: (a -> b -> b) -> b -> BinaryTree a -> b # foldl :: (b -> a -> b) -> b -> BinaryTree a -> b # foldl' :: (b -> a -> b) -> b -> BinaryTree a -> b # foldr1 :: (a -> a -> a) -> BinaryTree a -> a # foldl1 :: (a -> a -> a) -> BinaryTree a -> a # toList :: BinaryTree a -> [a] # null :: BinaryTree a -> Bool # length :: BinaryTree a -> Int # elem :: Eq a => a -> BinaryTree a -> Bool # maximum :: Ord a => BinaryTree a -> a # minimum :: Ord a => BinaryTree a -> a # sum :: Num a => BinaryTree a -> a # product :: Num a => BinaryTree a -> a #
Traversable BinaryTree Source #
Methods traverse :: Applicative f => (a -> f b) -> BinaryTree a -> f (BinaryTree b) # sequenceA :: Applicative f => BinaryTree (f a) -> f (BinaryTree a) # mapM :: Monad m => (a -> m b) -> BinaryTree a -> m (BinaryTree b) # sequence :: Monad m => BinaryTree (m a) -> m (BinaryTree a) #
Eq a => Eq (BinaryTree a) Source #
Methods (==) :: BinaryTree a -> BinaryTree a -> Bool # (/=) :: BinaryTree a -> BinaryTree a -> Bool #
Ord a => Ord (BinaryTree a) Source #
Methods compare :: BinaryTree a -> BinaryTree a -> Ordering # (<) :: BinaryTree a -> BinaryTree a -> Bool # (<=) :: BinaryTree a -> BinaryTree a -> Bool # (>) :: BinaryTree a -> BinaryTree a -> Bool # (>=) :: BinaryTree a -> BinaryTree a -> Bool # max :: BinaryTree a -> BinaryTree a -> BinaryTree a # min :: BinaryTree a -> BinaryTree a -> BinaryTree a #
Read a => Read (BinaryTree a) Source #
Methods readsPrec :: Int -> ReadS (BinaryTree a) # readList :: ReadS [BinaryTree a] # readPrec :: ReadPrec (BinaryTree a) # readListPrec :: ReadPrec [BinaryTree a] #
Show a => Show (BinaryTree a) Source #
Methods showsPrec :: Int -> BinaryTree a -> ShowS # show :: BinaryTree a -> String # showList :: [BinaryTree a] -> ShowS #
Generic (BinaryTree a) Source #
Associated Types type Rep (BinaryTree a) :: * -> * # Methods from :: BinaryTree a -> Rep (BinaryTree a) x # to :: Rep (BinaryTree a) x -> BinaryTree a #
NFData a => NFData (BinaryTree a) Source #
Methods rnf :: BinaryTree a -> () #
type Rep (BinaryTree a) Source #
type Rep (BinaryTree a) = D1 (MetaData "BinaryTree" "Data.BinaryTree" "hgeometry-0.6.0.0-ODn7ZyBfwj6IkLPAAzetJ" False) ((:+:) (C1 (MetaCons "Nil" PrefixI False) U1) (C1 (MetaCons "Internal" PrefixI False) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinaryTree a))) ((::) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinaryTree a)))))))

access :: BinaryTree a -> Maybe a Source #

Get the element stored at the root, if it exists

asBalancedBinTree :: [a] -> BinaryTree a Source #

Create a balanced binary tree

$O(n)$

foldBinaryUp :: b -> (a -> b -> b -> b) -> BinaryTree a -> BinaryTree (a, b) Source #

toRoseTree' :: BinaryTree a -> Maybe (Tree a) Source #

drawTree' :: Show a => BinaryTree a -> String Source #