|
|
| Line 1: |
Line 1: |
| − | <translate>
| |
| − | == Binary Trees == <!--T:1-->
| |
| − | * Create a data type <code>Tree</code> that defines binary tree where values are stored in leaves and also in branches.
| |
| − | </translate>
| |
| − |
| |
| − | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | data Tree a = Leaf a
| |
| − | | Branch a (Tree a) (Tree a) deriving (Show)
| |
| − | </syntaxhighlight>
| |
| − | </div>
| |
| − | <div style="clear:both"></div>
| |
| − |
| |
| − | <translate>
| |
| − | <!--T:2-->
| |
| − | * Prepare an example of a binary tree.
| |
| − | </translate>
| |
| − |
| |
| − | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | testTree1 :: Tree Int
| |
| − | testTree1 = Branch 12 (Branch 23 (Leaf 34) (Leaf 45)) (Leaf 55)
| |
| − |
| |
| − | testTree2 :: Tree Char
| |
| − | testTree2 = Branch 'a' (Branch 'b' (Leaf 'c') (Leaf 'd')) (Leaf 'e')
| |
| − | </syntaxhighlight>
| |
| − | </div>
| |
| − | <div style="clear:both"></div>
| |
| − |
| |
| − | <translate>
| |
| − | <!--T:3-->
| |
| − | * Create a function that sums all values stored in the tree.
| |
| − | </translate>
| |
| − |
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | sum' :: Tree Int -> Int
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | sum' :: Tree Int -> Int
| |
| − | sum' (Leaf x) = x
| |
| − | sum' (Branch x l r) = sum' l + x + sum' r
| |
| − | </syntaxhighlight>
| |
| − | </div>
| |
| − | <div style="clear:both"></div>
| |
| − |
| |
| − | <translate>
| |
| − | <!--T:4-->
| |
| − | * Create a function that extracts all values from the tree into an list.
| |
| − | </translate>
| |
| − |
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | toList :: Tree a -> [a]
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | toList :: Tree a -> [a]
| |
| − | toList (Leaf x) = [x]
| |
| − | toList (Branch x l r) = toList l ++ [x] ++ toList r
| |
| − | </syntaxhighlight>
| |
| − | </div>
| |
| − | <div style="clear:both"></div>
| |
| − |
| |
| − | <translate>
| |
| − | <!--T:5-->
| |
| − | * One possibility how to represent a tree in a textual form is <code>a(b(d,e),c(e,f(g,h)))</code>. Create functions that are able to read and store a tree in such a notation.
| |
| − | </translate>
| |
| − |
| |
| − | <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/b0EF9WQw-uw]]</div>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | toString :: Show a => Tree a -> String
| |
| − | fromString :: Read a => String -> Tree a
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | toString :: Show a => Tree a -> String
| |
| − | toString (Leaf x) = show x
| |
| − | toString (Branch x l r) = show x ++ "(" ++ (toString l) ++ "," ++ (toString r) ++ ")"
| |
| − |
| |
| − | fromString :: Read a => String -> Tree a
| |
| − | fromString inp = fst (fromString' inp) where
| |
| − | fromString' :: Read a => String -> (Tree a,String)
| |
| − | fromString' inp =
| |
| − | let
| |
| − | before = takeWhile (\x -> x /='(' && x /=',' && x/=')') inp
| |
| − | after = dropWhile (\x -> x /='(' && x /=',' && x/=')') inp
| |
| − | value = read before
| |
| − | in if null after || head after /= '(' then (Leaf value, after) else
| |
| − | let
| |
| − | (l,after') = fromString' (tail after)
| |
| − | (r,after'') = fromString' (tail after')
| |
| − | in (Branch value l r, tail after'')
| |
| − | </syntaxhighlight>
| |
| − | </div>
| |
| − | <div style="clear:both"></div>
| |
| − |
| |
| − |
| |
| | <translate> | | <translate> |
| | == Additional exercises == | | == Additional exercises == |
| − | * Create a function that counts all leaves in the tree.
| |
| − | </translate>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | leafCount :: Tree a -> Int
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Create a function that counts all branches in the tree.
| |
| − | </translate>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | branchCount :: Tree a -> Int
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Create a function that checks whether a given element is stored in the tree.
| |
| − | </translate>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | contains :: Eq a => Tree a -> a -> Bool
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Create a function that finds a maximum value stored in the tree.
| |
| − | </translate>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | maxTree :: Ord a => Tree a -> a
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Create a function that returns a number of elements greater than a given value.
| |
| − | </translate>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | greaterThan :: Ord a => Tree a -> a -> Int
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Create a function that returns the depth of a tree.
| |
| − | </translate>
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | depthTree :: Tree a -> Int
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Consider the following alternative definition of the binary tree.
| |
| − | </translate>
| |
| − |
| |
| − | <syntaxhighlight lang="Haskell">
| |
| − | data Tree2 a = Null | Branch a (Tree2 a) (Tree2 a)
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | <translate>
| |
| − | * Is this definition equivalent to the previous one? If not, explain why and give an example of a tree that can be constructed with the first definition but not with the second one or vice versa.
| |
| − | </translate>
| |
| − |
| |
| − | <translate>
| |
| − | * Implement all functions above adjusted for the alternative definition of the binary tree.
| |
| | </translate> | | </translate> |
| − |
| |
| − | == m-ary Trees ==
| |
| | | | |
| | <translate> | | <translate> |
