FuzzyBot: Updating to match new version of source page

2023-11-15T09:58:33Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2022-11-14T12:35:47Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2021-10-21T08:37:25Z

Updating to match new version of source page

New page

== Abstract data types ==

<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Stx4YcQbZzg]]</div>

* Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) <code>Stack</code>] with following functions:

<syntaxhighlight lang="Haskell">
push :: a -> Stack a -> Stack a
pop :: Stack a -> Stack a
top :: Stack a -> a
isEmpty :: Stack a ->Bool
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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
</syntaxhighlight>
</div>
<div style="clear:both"></div>

* Create an implementation of the abstract data type [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) <code>Queue</code>] with following functions:

<syntaxhighlight lang="Haskell">
isEmpty :: Queue a -> Bool
addQ :: a -> Queue a -> Queue a
remQ :: Queue q -> (a, Queue a)
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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"
</syntaxhighlight>
</div>
<div style="clear:both"></div>

← Older revision		Revision as of 09:58, 15 November 2023
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 ==

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

FP Laboratory 10/en - Revision history

FuzzyBot: Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

FuzzyBot: Updating to match new version of source page