PFP Laboratory 6
Jump to navigation
Jump to search
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
- 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.
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'')
Complex data structure
Consider following data structure representing some kind of GUI.
data Point = Point {column::Int,row::Int} deriving (Show)
data Position = Position {leftTopCorner :: Point, width :: Int, height :: Int}
data Component
= TextBox {name :: String, position :: Position, text :: String}
| Button {name :: String, position :: Position, text :: String}
| Container {name :: String, children :: [Component]}
As an example, we can use following data structure.
gui :: Component
gui =
Container "My App"
[ Container "Menu"
[ Button "btn_new" (Position (Point 0 0) 100 20) "New",
Button "btn_open" (Position (Point 100 0) 100 20) "Open",
Button "btn_close" (Position (Point 200 0) 100 20) "Close"
],
Container "Body" [TextBox "textbox_1" (Position (Point 0 20) 300 500) "Some text goes here"],
Container "Footer" []
]
- Add the data type
Component
into the type classShow
.
The result for our data from previous example should be something like this.
ghci> gui
Container - My App
Container - Menu
(0,0)[100,20] Button[btn_new]: New
(100,0)[100,20] Button[btn_open]: Open
(200,0)[100,20] Button[btn_close]: Close
Container - Body
(0,20)[300,500] TextBox[textbox_1]: Some text goes here
Container - Footer
instance Show Position where
show (Position (Point col row) width height) = "(" ++ show col ++ "," ++ show row ++ ")["++ show width++","++ show height++"]"
instance Show Component where
show :: Component -> String
show gui = showIndent "" gui where
showIndent ind (TextBox name position text) = ind ++ show position ++ " TextBox[" ++ name ++ "]: " ++ text ++"\n"
showIndent ind (Button name position text) = ind ++ show position ++ " Button[" ++ name ++ "]: " ++ text ++"\n"
showIndent ind (Container name children) = let
inner = concat[showIndent (ind++"\t") c |c<-children]
in ind ++ "Container - " ++ name ++ "\n" ++ inner
- Cerate a function
insertInto
, it will insert an element into the existing container from a GUI. The functions parameters will be:- first parameter will be the GUI, where we are inserting the new element;
- second parameter is the name of the container, where we insert the new element, you can safely assume, that it will always exist. The element will be placed as last in the container;
- last parameter is the inserted element.
insertInto :: Component -> String -> Component -> Component
ghci> insertInto gui "Footer" (TextBox "Done" (Position (Point 0 500) 300 10) "We are done!")
Container - My App
Container - Menu
(0,0)[100,20] Button[btn_new]: New
(100,0)[100,20] Button[btn_open]: Open
(200,0)[100,20] Button[btn_close]: Close
Container - Body
(0,20)[300,500] TextBox[textbox_1]: Some text goes here
Container - Footer
(0,500)[300,10] TextBox[Done]: We are done!
insertInto :: Component -> String -> Component -> Component
insertInto (Container cName children ) toName element
| cName == toName = Container cName (children++[element])
| otherwise = Container cName [insertInto c toName element |c<-children]
insertInto x toName element = x
- Extend the definition of a button in our GUI as follows.
data Event = MouseEvent Point
| KeyEvent {keyPressed::Char} deriving (Show)
...
| Button {name :: String, position :: Position, text :: String, onClick :: Maybe (Event -> String)}
...
Our onClick is a function, that will be fired when the button is clicked on. The parameter of this function is data describing the firing event.
...
[ Button "btn_new" (Position (Point 0 0) 100 20) "New" (Just (\event -> "Clicked on new button.")),
Button "btn_open" (Position (Point 100 0) 100 20) "Open" Nothing,
Button "btn_close" (Position (Point 200 0) 100 20) "Close" (Just (\event -> "Clicked on close button.")) ]
...
- Create a function
clickOnButton
that will take our GUI and an event. If it is a mouse event, and the position where we have clicked is inside some of the buttons from the gui, then it evaluates the corespondingonClick
function and the result will be produced string. In all other cases, the result will beNothing
.
clickOnButton :: Component -> Event -> Maybe String
ghci> clickOnButton gui (MouseEvent (Point 5 5))
Just "Clicked on new button."
ghci> clickOnButton gui (MouseEvent (Point 205 5))
Just "Clicked on close button."
ghci> clickOnButton gui (MouseEvent (Point 205 50))
Nothing
isInside :: Point -> Position -> Bool
isInside (Point pCol pRow) (Position (Point cornerCol cornerRow) width height) =
cornerCol <= pCol && pCol <= cornerCol + width && cornerRow <= pRow && pRow <= cornerRow + height
getFirstOrNothing :: [Maybe a] -> Maybe a
getFirstOrNothing [] = Nothing
getFirstOrNothing (Nothing:xs) = getFirstOrNothing xs
getFirstOrNothing (Just x: xs) = Just x
clickOnButton :: Component -> Event -> Maybe String
clickOnButton (Button {position = pos, onClick = (Just func)}) (MouseEvent point) | isInside point pos = Just (func (MouseEvent point))
clickOnButton (Container {children=inner}) event = getFirstOrNothing [clickOnButton c event |c<-inner]
clickOnButton _ _ = Nothing