Difference between revisions of "FP Laboratory 10/en"

From Marek Běhálek Wiki
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.
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"