FP Laboratory 10 - Revision history

Beh01: Marked this version for translation

2023-11-15T09:57:20Z

Marked this version for translation

Beh01 at 09:56, 15 November 2023

2023-11-15T09:56:20Z

Beh01 at 09:38, 15 November 2023

2023-11-15T09:38:46Z

Beh01 at 09:36, 15 November 2023

2023-11-15T09:36:23Z

Beh01 at 09:32, 15 November 2023

2023-11-15T09:32:56Z

Beh01 at 09:31, 15 November 2023

2023-11-15T09:31:08Z

Beh01 at 12:35, 14 November 2022

2022-11-14T12:35:28Z

Fai0013: Marked this version for translation

2021-10-21T08:24:38Z

Marked this version for translation

Fai0013 at 08:24, 21 October 2021

2021-10-21T08:24:00Z

Beh01: /* Abstract data types */

2020-11-02T11:52:01Z

Abstract data types

@@ Line 1: / Line 1: @@
 <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.
 </translate>
@@ Line 13: / Line 13: @@
 <translate>
 * Prepare an example of a binary tree.
 </translate>
@@ Line 28: / Line 29: @@
 <translate>
 * Create a function that sums all values stored in the tree.
 </translate>
@@ Line 45: / Line 47: @@
 <translate>
 * Create a function that extracts all values from the tree into an list.
 </translate>
@@ Line 62: / Line 65: @@
 <translate>
 * Create a function that finds a maximum value stored in the tree.
 </translate>
@@ Line 78: / Line 82: @@
 <translate>
 * Create a function that returns the depth of a tree.
 </translate>
@@ Line 94: / Line 99: @@
 <translate>
 * Create a function that returns as list elements bigger than a given value.
 </translate>
@@ Line 112: / Line 118: @@
 <translate>
 * 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>
@@ Line 145: / Line 152: @@
 <translate>
-== Additional exercises ==
+== Additional exercises == <!--T:12-->
 * Create a function that counts all leaves in the tree.
 </translate>
@@ Line 153: / Line 160: @@
 <translate>
 * Create a function that counts all branches in the tree.
 </translate>
@@ Line 160: / Line 168: @@
 <translate>
 * Create a function that checks whether a given element is stored in the tree.
 </translate>
@@ Line 167: / Line 176: @@
 <translate>
 * Create a function that returns a number of elements greater than a given value.
 </translate>
@@ Line 174: / Line 184: @@
 <translate>
 * Consider the following alternative definition of the binary tree.
 </translate>
@@ Line 182: / Line 193: @@
 <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>
-== Abstract data types ==
+== Abstract data types == <!--T:19-->
 </translate>
@@ Line 196: / Line 209: @@
 <translate>
 * Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) <code>Stack</code>] with following functions:
 </translate>
@@ Line 231: / Line 245: @@
 <translate>
 * Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) <code>Queue</code>] with following functions:
 </translate>

@@ Line 70: / Line 70: @@
 <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 <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>
 </div>
@@ Line 86: / Line 86: @@
 <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 <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>
 </div>
@@ Line 102: / Line 102: @@
 <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 <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 = []
 </syntaxhighlight>
 </div>

@@ Line 67: / Line 67: @@
 maxTree :: Ord a => Tree a -> a
 </syntaxhighlight>
 <translate>
@@ Line 74: / Line 83: @@
 depthTree :: Tree a -> Int
 </syntaxhighlight>
 <translate>
@@ Line 81: / Line 99: @@
 getGreaterElements :: Ord a => Tree a -> a -> [a]
 </syntaxhighlight>
 <translate>

@@ Line 60: / Line 60: @@
 </div>
 <div style="clear:both"></div>
 <translate>
@@ Line 114: / Line 135: @@
 <syntaxhighlight lang="Haskell">
 contains :: Eq a => Tree a -> a -> Bool
 </syntaxhighlight>
@@ Line 128: / Line 142: @@
 <syntaxhighlight lang="Haskell">
 greaterThan :: Ord a => Tree a -> a -> Int
 </syntaxhighlight>

@@ Line 94: / Line 94: @@
 <div style="clear:both"></div>
 <translate>
-== Additional exercises ==
+* Create a function that returns a number of elements greater than a given value.
-=== Abstract data types ===
+</translate>
 </translate>

@@ Line 49: / Line 49: @@
 isEmpty :: Queue a -> Bool
 addQ :: a -> Queue a -> Queue a
-remQ :: Queue q -> (a, Queue a)
+remQ :: Queue a -> (a, Queue a)
 </syntaxhighlight>