Problems.BinaryTrees

Description

Supporting definitions for binary tree problems.

Synopsis

Documentation

data Tree a Source #

A binary tree.

A Tree of type a consists of either an Empty node, or a Branch containing one value of type a with exactly two subtrees of type a.

Notes

Expand

This is not the problem 54A from the original Ninety-Nine Haskell Problems. As it also mentions, there is nothing to do here except making sure code compiles correctly, thanks to Haskell's strict typing and the way Tree is defined.

Instead, the problem was replaced by the simple problems of implementing given binary trees as Haskell values. I.e., turn the examples from the original problem into simple problems to solve.

Constructors

 Empty Branch a (Tree a) (Tree a)

Instances

Instances details
 Generic (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Associated Typestype Rep (Tree a) :: Type -> Type # Methodsfrom :: Tree a -> Rep (Tree a) x #to :: Rep (Tree a) x -> Tree a # Show a => Show (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees MethodsshowsPrec :: Int -> Tree a -> ShowS #show :: Tree a -> String #showList :: [Tree a] -> ShowS # NFData a => NFData (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Methodsrnf :: Tree a -> () # Eq a => Eq (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Methods(==) :: Tree a -> Tree a -> Bool #(/=) :: Tree a -> Tree a -> Bool # Ord a => Ord (Tree a) Source # An arbitrary total ordering for Tree.Defines an order for a set of Trees. Not intended to support solving problems. Instance detailsDefined in Problems.BinaryTrees Methodscompare :: Tree a -> Tree a -> Ordering #(<) :: Tree a -> Tree a -> Bool #(<=) :: Tree a -> Tree a -> Bool #(>) :: Tree a -> Tree a -> Bool #(>=) :: Tree a -> Tree a -> Bool #max :: Tree a -> Tree a -> Tree a #min :: Tree a -> Tree a -> Tree a # type Rep (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees type Rep (Tree a) = D1 ('MetaData "Tree" "Problems.BinaryTrees" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) (C1 ('MetaCons "Empty" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Branch" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a)))))

Support functions

treeSize :: Tree a -> Int Source #

Returns the number of nodes in a binary tree.

treeHeight :: Tree a -> Int Source #

Returns the height of a binary tree.

printTreeList :: (Show a, Ord a) => [Tree a] -> IO () Source #

Prints a list of Trees.

For two lists with the same trees, except for perhaps different order, the output will be the same.

Not intended to support solving problems.