Difference between revisions of "FP Laboratory 10"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Marked this version for translation)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
<translate>
 
<translate>
== Binary Trees ==  
+
== Binary Trees == <!--T:4-->
 
* Create a data type <code>Tree</code> that defines binary tree where values are stored in leaves and also in branches.  
 
* Create a data type <code>Tree</code> that defines binary tree where values are stored in leaves and also in branches.  
 
</translate>
 
</translate>
Line 13: Line 13:
  
 
<translate>
 
<translate>
 +
<!--T:5-->
 
* Prepare an example of a binary tree.
 
* Prepare an example of a binary tree.
 
</translate>
 
</translate>
Line 28: Line 29:
  
 
<translate>
 
<translate>
 +
<!--T:6-->
 
* Create a function that sums all values stored in the tree.
 
* Create a function that sums all values stored in the tree.
 
</translate>
 
</translate>
Line 45: Line 47:
  
 
<translate>
 
<translate>
 +
<!--T:7-->
 
* Create a function that extracts all values from the tree into an list.
 
* Create a function that extracts all values from the tree into an list.
 
</translate>
 
</translate>
Line 62: Line 65:
  
 
<translate>
 
<translate>
 +
<!--T:8-->
 
* Create a function that finds a maximum value stored in the tree.
 
* Create a function that finds a maximum value stored in the tree.
 
</translate>
 
</translate>
Line 70: Line 74:
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
sum' :: Tree Int -> Int
+
maxTree :: Ord a => Tree a -> a
sum' (Leaf x) = x
+
maxTree (Leaf x) = x
sum' (Branch x l r) = sum' l + x + sum' r
+
maxTree (Branch x l r) = maximum [x, maxTree l, maxTree r]
 
</syntaxhighlight>
 
</syntaxhighlight>
 
</div>
 
</div>
Line 78: Line 82:
  
 
<translate>
 
<translate>
 +
<!--T:9-->
 
* Create a function that returns the depth of a tree.
 
* Create a function that returns the depth of a tree.
 
</translate>
 
</translate>
Line 86: Line 91:
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
sum' :: Tree Int -> Int
+
depthTree :: Tree a -> Int
sum' (Leaf x) = x
+
depthTree (Leaf x) = 1
sum' (Branch x l r) = sum' l + x + sum' r
+
depthTree (Branch x l r) = max (depthTree l) (depthTree r) + 1
 
</syntaxhighlight>
 
</syntaxhighlight>
 
</div>
 
</div>
Line 94: Line 99:
  
 
<translate>
 
<translate>
 +
<!--T:10-->
 
* Create a function that returns as list elements bigger than a given value.
 
* Create a function that returns as list elements bigger than a given value.
 
</translate>
 
</translate>
Line 102: Line 108:
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
sum' :: Tree Int -> Int
+
getGreaterElements :: Ord a => Tree a -> a -> [a]
sum' (Leaf x) = x
+
getGreaterElements (Leaf x) y | x > y = [x]
sum' (Branch x l r) = sum' l + x + sum' r
+
                              | otherwise = []
 +
getGreaterElements (Branch x l r) y | x > y = [x] ++  getGreaterElements l y ++ getGreaterElements r y
 +
                                    | otherwise = getGreaterElements l y ++ getGreaterElements r y
 
</syntaxhighlight>
 
</syntaxhighlight>
 
</div>
 
</div>
Line 110: Line 118:
  
 
<translate>
 
<translate>
 +
<!--T:11-->
 
* 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.
 
* 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>  
 
</translate>  
Line 143: Line 152:
  
 
<translate>
 
<translate>
== Additional exercises ==
+
== Additional exercises == <!--T:12-->
 
* Create a function that counts all leaves in the tree.
 
* Create a function that counts all leaves in the tree.
 
</translate>
 
</translate>
Line 151: Line 160:
  
 
<translate>
 
<translate>
 +
<!--T:13-->
 
* Create a function that counts all branches in the tree.
 
* Create a function that counts all branches in the tree.
 
</translate>
 
</translate>
Line 158: Line 168:
  
 
<translate>
 
<translate>
 +
<!--T:14-->
 
* Create a function that checks whether a given element is stored in the tree.  
 
* Create a function that checks whether a given element is stored in the tree.  
 
</translate>
 
</translate>
Line 165: Line 176:
  
 
<translate>
 
<translate>
 +
<!--T:15-->
 
* Create a function that returns a number of elements greater than a given value.
 
* Create a function that returns a number of elements greater than a given value.
 
</translate>
 
</translate>
Line 172: Line 184:
  
 
<translate>
 
<translate>
 +
<!--T:16-->
 
* Consider the following alternative definition of the binary tree.
 
* Consider the following alternative definition of the binary tree.
 
</translate>
 
</translate>
Line 180: Line 193:
  
 
<translate>
 
<translate>
 +
<!--T:17-->
 
* 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.
 
* 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>
  
 
<translate>
 
<translate>
 +
<!--T:18-->
 
* Implement all functions above adjusted for the alternative definition of the binary tree.
 
* Implement all functions above adjusted for the alternative definition of the binary tree.
 
</translate>
 
</translate>
  
 
<translate>
 
<translate>
== Abstract data types ==
+
== Abstract data types == <!--T:19-->
 
</translate>
 
</translate>
  
Line 194: Line 209:
  
 
<translate>
 
<translate>
 +
<!--T:20-->
 
* Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) <code>Stack</code>] with following functions:
 
* Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) <code>Stack</code>] with following functions:
 
</translate>
 
</translate>
Line 229: Line 245:
  
 
<translate>
 
<translate>
 +
<!--T:21-->
 
* Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) <code>Queue</code>] with following functions:
 
* Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) <code>Queue</code>] with following functions:
 
</translate>
 
</translate>

Latest revision as of 09:57, 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.
Video logo.png
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

Video logo.png
  • 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"