Difference between revisions of "FP Laboratory 11/cs"
Jump to navigation
Jump to search
(Created page with "== Binární stromy == * Implementujte datový typ <code>Tree</code>, který definuje binární strom, který ukládá hodnoty v listech a také ve větvich.") |
(Updating to match new version of source page) |
||
(28 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | == | + | == Složitá datová struktura == |
− | + | Uvažujme následující datovou strukturu reprezentující nějaký druh grafického uživatelského rozhraní. | |
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | 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]} | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Jako příklad můžeme použít následující datovou strukturu. | ||
− | |||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | 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" [] | ||
+ | ] | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
− | * | + | * Přidejte typ <code>Component</code> do typove třídy <code>Show</code>. |
+ | |||
+ | Výsledek pro naše data z předchozího příkladu by měl vypadat takto. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | 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 | ||
+ | </syntaxhighlight> | ||
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | ||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | 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 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * | + | * Vytvořte funkci <code>insertInto</code>, která vloží prvek do existujícího kontejneru z GUI. Parametry funkce budou: |
+ | ** prvním parametrem bude GUI, do kterého budeme vkládat nový prvek; | ||
+ | ** druhým parametrem bude název kontejneru, do kterého vkládáme nový prvek, lze bezpečně předpokládat, že bude vždy existovat. Prvek bude v kontejneru umístěn jako poslední; | ||
+ | ** posledním parametrem je vložený prvek. | ||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | insertInto :: Component -> String -> Component -> Component | |
+ | </syntaxhighlight> | ||
+ | |||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | 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! | ||
</syntaxhighlight> | </syntaxhighlight> | ||
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | ||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | 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 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * | + | * Rozšiřte definici tlačítka v našem GUI takto. |
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | data Event = MouseEvent Point | ||
+ | | KeyEvent {keyPressed::Char} deriving (Show) | ||
+ | ... | ||
+ | | Button {name :: String, position :: Position, text :: String, onClick :: Maybe (Event -> String)} | ||
+ | ... | ||
+ | </syntaxhighlight> | ||
+ | Naše '''onClick''' je funkce, která se spustí po kliknutí na tlačítko. Parametrem této funkce jsou data popisující událost, která se osluhu spustila. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | ... | ||
+ | [ 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.")) ] | ||
+ | ... | ||
+ | </syntaxhighlight> | ||
+ | * Vytvořte funkci <code>clickOnButton</code>, která dostane naše GUI a nějakou událost. Pokud je parametrem instance <code>MouseEvent</code> a pozice, na kterou jsme klikli, je uvnitř některého z tlačítek GUI, pak vyhodnotí odpovídající funkci <code>onClick</code> a výsledkem bude získáný řetězec. Ve všech ostatních případech bude výsledkem <code>Nothing</code>. | ||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | clickOnButton :: Component -> Event -> Maybe String | |
+ | </syntaxhighlight> | ||
+ | |||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | 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 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | <div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution"> | ||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | 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 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * | + | == Doplňková cvičení == |
+ | |||
+ | * Uvažujme následující definici a příklad m-árního stromu. | ||
− | |||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | data MTree a = MTree a [MTree a] | |
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
<syntaxhighlight lang="Haskell"> | <syntaxhighlight lang="Haskell"> | ||
− | + | testTree1 :: MTree Int | |
− | + | testTree1 = MTree 1 [(MTree 2 [(MTree 3 []),(MTree 4 [(MTree 5 []),(MTree 6 [])]), (MTree 7 []),(MTree 8 [])]), (MTree 9 [])] | |
− | + | </syntaxhighlight> | |
+ | |||
+ | * Vytvořte funkci, která sečte všechny hodnoty uložené ve stromu m-ary. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | msum :: MTree Int -> Int | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci, která extrahuje všechny hodnoty z m-arního strimu do seznamu. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | mToList :: MTree a -> [a] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci, která spočítá všechny listy v m-arním stromu. | ||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | mLeafCount :: MTree a -> Int | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci, která najde maximální hodnotu uloženou v m-árním stromu. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | mMaxTree :: Ord a => MTree a -> a | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvoření funkce, která zkontroluje, zda je daný prvek uložen v m-árním | ||
+ | stromu. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell"> | ||
+ | mContains :: Eq a => MTree a -> a -> Bool | ||
+ | </syntaxhighlight> | ||
− | + | * Vytvoření funkce, která vrátí počet prvků větších než zadaná hodnota. | |
− | + | <syntaxhighlight lang="Haskell"> | |
− | + | mGreaterThan :: Ord a => MTree a -> a -> Int | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− |
Latest revision as of 07:29, 16 November 2023
Složitá datová struktura
Uvažujme následující datovou strukturu reprezentující nějaký druh grafického uživatelského rozhraní.
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]}
Jako příklad můžeme použít následující datovou strukturu.
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" []
]
- Přidejte typ
Component
do typove třídyShow
.
Výsledek pro naše data z předchozího příkladu by měl vypadat takto.
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
- Vytvořte funkci
insertInto
, která vloží prvek do existujícího kontejneru z GUI. Parametry funkce budou:- prvním parametrem bude GUI, do kterého budeme vkládat nový prvek;
- druhým parametrem bude název kontejneru, do kterého vkládáme nový prvek, lze bezpečně předpokládat, že bude vždy existovat. Prvek bude v kontejneru umístěn jako poslední;
- posledním parametrem je vložený prvek.
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
- Rozšiřte definici tlačítka v našem GUI takto.
data Event = MouseEvent Point
| KeyEvent {keyPressed::Char} deriving (Show)
...
| Button {name :: String, position :: Position, text :: String, onClick :: Maybe (Event -> String)}
...
Naše onClick je funkce, která se spustí po kliknutí na tlačítko. Parametrem této funkce jsou data popisující událost, která se osluhu spustila.
...
[ 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.")) ]
...
- Vytvořte funkci
clickOnButton
, která dostane naše GUI a nějakou událost. Pokud je parametrem instanceMouseEvent
a pozice, na kterou jsme klikli, je uvnitř některého z tlačítek GUI, pak vyhodnotí odpovídající funkcionClick
a výsledkem bude získáný řetězec. Ve všech ostatních případech bude výsledkemNothing
.
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
Doplňková cvičení
- Uvažujme následující definici a příklad m-árního stromu.
data MTree a = MTree a [MTree a]
testTree1 :: MTree Int
testTree1 = MTree 1 [(MTree 2 [(MTree 3 []),(MTree 4 [(MTree 5 []),(MTree 6 [])]), (MTree 7 []),(MTree 8 [])]), (MTree 9 [])]
- Vytvořte funkci, která sečte všechny hodnoty uložené ve stromu m-ary.
msum :: MTree Int -> Int
- Vytvořte funkci, která extrahuje všechny hodnoty z m-arního strimu do seznamu.
mToList :: MTree a -> [a]
- Vytvořte funkci, která spočítá všechny listy v m-arním stromu.
mLeafCount :: MTree a -> Int
- Vytvořte funkci, která najde maximální hodnotu uloženou v m-árním stromu.
mMaxTree :: Ord a => MTree a -> a
- Vytvoření funkce, která zkontroluje, zda je daný prvek uložen v m-árním
stromu.
mContains :: Eq a => MTree a -> a -> Bool
- Vytvoření funkce, která vrátí počet prvků větších než zadaná hodnota.
mGreaterThan :: Ord a => MTree a -> a -> Int