Difference between revisions of "FP Laboratory 10/en"
Jump to navigation
Jump to search
(Updating to match new version of source page) |
(Updating to match new version of source page) |
||
Line 1: | Line 1: | ||
+ | == Binary Trees == | ||
+ | * Create a data type <code>Tree</code> that defines binary tree where values are stored in leaves and also in branches. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | * Prepare an example of a binary tree. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | * Create a function that sums all values stored in the tree. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | * Create a function that extracts all values from the tree into an list. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | * Create a function that finds a maximum value stored in the tree. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | maxTree :: Ord a => Tree a -> a | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | maxTree :: Ord a => Tree a -> a | ||
+ | maxTree (Leaf x) = x | ||
+ | maxTree (Branch x l r) = maximum [x, maxTree l, maxTree r] | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | <div style="clear:both"></div> | ||
+ | |||
+ | * Create a function that returns the depth of a tree. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | depthTree :: Tree a -> Int | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | depthTree :: Tree a -> Int | ||
+ | depthTree (Leaf x) = 1 | ||
+ | depthTree (Branch x l r) = max (depthTree l) (depthTree r) + 1 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | <div style="clear:both"></div> | ||
+ | |||
+ | * Create a function that returns as list elements bigger than a given value. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | getGreaterElements :: Ord a => Tree a -> a -> [a] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | getGreaterElements :: Ord a => Tree a -> a -> [a] | ||
+ | getGreaterElements (Leaf x) y | x > y = [x] | ||
+ | | otherwise = [] | ||
+ | getGreaterElements (Branch x l r) y | x > y = [x] ++ getGreaterElements l y ++ getGreaterElements r y | ||
+ | | otherwise = getGreaterElements l y ++ getGreaterElements r y | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | <div style="clear:both"></div> | ||
+ | |||
+ | * 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. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | == Additional exercises == | ||
+ | * Create a function that counts all leaves in the tree. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | leafCount :: Tree a -> Int | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Create a function that counts all branches in the tree. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | branchCount :: Tree a -> Int | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Create a function that checks whether a given element is stored in the tree. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | contains :: Eq a => Tree a -> a -> Bool | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Create a function that returns a number of elements greater than a given value. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | greaterThan :: Ord a => Tree a -> a -> Int | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Consider the following alternative definition of the binary tree. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | data Tree2 a = Null | Branch a (Tree2 a) (Tree2 a) | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * 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. | ||
+ | |||
+ | * Implement all functions above adjusted for the alternative definition of the binary tree. | ||
+ | |||
== Abstract data types == | == Abstract data types == | ||
Latest revision as of 09:58, 15 November 2023
Binary Trees
- Create a data type
Tree
that defines binary tree where values are stored in leaves and also in branches.
data Tree a = Leaf a
| Branch a (Tree a) (Tree a) deriving (Show)
- Prepare an example of a binary tree.
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')
- Create a function that sums all values stored in the tree.
sum' :: Tree Int -> Int
sum' :: Tree Int -> Int
sum' (Leaf x) = x
sum' (Branch x l r) = sum' l + x + sum' r
- Create a function that extracts all values from the tree into an list.
toList :: Tree a -> [a]
toList :: Tree a -> [a]
toList (Leaf x) = [x]
toList (Branch x l r) = toList l ++ [x] ++ toList r
- Create a function that finds a maximum value stored in the tree.
maxTree :: Ord a => Tree a -> a
maxTree :: Ord a => Tree a -> a
maxTree (Leaf x) = x
maxTree (Branch x l r) = maximum [x, maxTree l, maxTree r]
- Create a function that returns the depth of a tree.
depthTree :: Tree a -> Int
depthTree :: Tree a -> Int
depthTree (Leaf x) = 1
depthTree (Branch x l r) = max (depthTree l) (depthTree r) + 1
- Create a function that returns as list elements bigger than a given value.
getGreaterElements :: Ord a => Tree a -> a -> [a]
getGreaterElements :: Ord a => Tree a -> a -> [a]
getGreaterElements (Leaf x) y | x > y = [x]
| otherwise = []
getGreaterElements (Branch x l r) y | x > y = [x] ++ getGreaterElements l y ++ getGreaterElements r y
| otherwise = getGreaterElements l y ++ getGreaterElements r y
- One possibility how to represent a tree in a textual form is
a(b(d,e),c(e,f(g,h)))
. Create functions that are able to read and store a tree in such a notation.
toString :: Show a => Tree a -> String
fromString :: Read a => String -> Tree a
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'')
Additional exercises
- Create a function that counts all leaves in the tree.
leafCount :: Tree a -> Int
- Create a function that counts all branches in the tree.
branchCount :: Tree a -> Int
- Create a function that checks whether a given element is stored in the tree.
contains :: Eq a => Tree a -> a -> Bool
- Create a function that returns a number of elements greater than a given value.
greaterThan :: Ord a => Tree a -> a -> Int
- Consider the following alternative definition of the binary tree.
data Tree2 a = Null | Branch a (Tree2 a) (Tree2 a)
- 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.
- Implement all functions above adjusted for the alternative definition of the binary tree.
Abstract data types
- Create an implementation of the abstract data type
Stack
with following functions:
push :: a -> Stack a -> Stack a
pop :: Stack a -> Stack a
top :: Stack a -> a
isEmpty :: Stack a ->Bool
module Stack(Stack, emptyS, push, pop, top, isEmpty) where
data Stack a = Stack [a] deriving Show
emptyS :: Stack a
emptyS = Stack []
push :: a -> Stack a -> Stack a
push x (Stack y) = Stack (x:y)
pop :: Stack a -> Stack a
pop (Stack (_:xs)) = Stack xs
top :: Stack a -> a
top (Stack (x:_)) = x
isEmpty :: Stack a ->Bool
isEmpty (Stack []) = True
isEmpty _ = False
- Create an implementation of the abstract data type
Queue
with following functions:
isEmpty :: Queue a -> Bool
addQ :: a -> Queue a -> Queue a
remQ :: Queue a -> (a, Queue a)
module Queue(Queue, emptyQ, isEmptyQ, addQ, remQ) where
data Queue a = Qu [a] deriving Show
emptyQ :: Queue a
emptyQ = Qu []
isEmptyQ :: Queue a -> Bool
isEmptyQ (Qu q) = null q
addQ :: a -> Queue a -> Queue a
addQ x (Qu xs) = Qu (xs++[x])
remQ :: Queue a -> (a,Queue a)
remQ q@(Qu xs) | not (isEmptyQ q) = (head xs, Qu (tail xs))
| otherwise = error "remQ"