FP Laboratory 11/en - Revision history

FuzzyBot: Updating to match new version of source page

2024-11-19T11:33:09Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2023-11-16T07:30:31Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2023-11-15T14:36:55Z

Updating to match new version of source page

Show changes

FuzzyBot: Updating to match new version of source page

2021-10-21T09:19:17Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2021-10-21T09:02:27Z

Updating to match new version of source page

New page

== 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 counts the values stored in the leaves.

<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 leaves 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>

* 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>

@@ Line 91: / Line 91: @@
      | otherwise = Container cName [insertInto c toName element  |c<-children]
 insertInto x toName element = x
 </syntaxhighlight>
 </div>

@@ Line 18: / Line 18: @@
 gui :: Component
 gui =
-   Container
+   Container "My App"
-    "My App"
+     [ Container "Menu"
          [ Button "btn_new" (Position (Point 0 0) 100 20) "New",
            Button "btn_open" (Position (Point 100 0) 100 20) "Open",

@@ Line 23: / Line 23: @@
 <div style="clear:both"></div>
-* Create a function that counts the values stored in the leaves.
+* Create a function that sums all values stored in the tree.
 <syntaxhighlight lang="Haskell">
@@ Line 38: / Line 38: @@
 <div style="clear:both"></div>
-* Create a function that extracts all values from the leaves into an list.
+* Create a function that extracts all values from the tree into an list.
 <syntaxhighlight lang="Haskell">