Histogram¶
Useful Files¶
Úloha 3.1 – histogram¶
Definujte funkciu, ktorá vykreslí histogram zo zadaného zoznamu prostredníctvom znakov |, kde výška každého stĺpca zodpovedá počtu výskytov príslušného čísla v zozname. Pričom nech je vykreslená aj legenda — čísla položiek dole a hodnoty naľavo. Pritom nech je v legende vypísaná len každá piata hodnota. Napr. pre zoznam uvedený v kóde nižšie nech je výsledok takýto:
*Main> putStr (histogram values)
10 |
| |
| | |
| | | | |
| | | | | | |
5 | | | | | | | | | |
| | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |
0 5 10 15
Domáca úloha 4 – Histogram v Haskelli¶
Navigácia¶
- Zadanie
- Spustenie
- Základná myšlienka riešenia
- Prehľad funkcií
- Podrobný popis kódu
- 5.1 Importy
- 5.2 Vstupné dáta –
values - 5.3
histogram– hlavná funkcia - 5.4
countOccurrences– počítanie výskytov - 5.5
mostFrequent– najväčší počet - 5.6
allOccurrences– výskyty aj pre chýbajúce čísla - 5.7
drawRow– jeden riadok tela - 5.8
drawRows– všetky riadky tela (rekurzia) - 5.9
legendCell– bunka legendy - 5.10
legendLine– spodná legenda - 5.11
legendColumn– ľavá legenda - 5.12
alignRight– zarovnanie doprava - 5.13
sideBySideastacked– skladanie blokov - 5.14
main - Celý tok dát na menšom príklade
- Použité koncepty Haskellu
Stručne¶
Program vykreslí textový histogram: pre každé číslo zo zoznamu nakreslí stĺpec zo znakov |, ktorého výška je počet výskytov tohto čísla. Vľavo a dole je legenda s každou piatou hodnotou.
Postup v skratke:
- Spočítanie výskytov –
sort+groupzoskupí rovnaké čísla a z každej skupiny vznikne dvojica(číslo, počet). Chýbajúce čísla sa doplnia s počtom 0, aby stĺpce sedeli s legendou. - Výška histogramu – najväčší počet výskytov nájdený cez
maximumBy. - Telo – rekurzívne
drawRowsvykreslí riadky zhora nadol. V každom riadku má stĺpec" |", ak siaha aspoň do tejto výšky, inak" ". - Legendy – spodný riadok s číslami položiek a ľavý stĺpec s výškami, oba z rovnakej funkcie
legendCell. - Poskladanie –
stackeddá legendu pod telo,sideBySideprilepí ľavú legendu,unlinesz toho urobí jedenString.
Všetko sedí pod sebou vďaka jednému pravidlu: každá bunka má presne 2 znaky.
1. Zadanie¶
Napísať funkciu histogram :: [Int] -> String, ktorá zo zoznamu celých čísel vykreslí textový histogram zo znakov |. Výška každého stĺpca zodpovedá počtu výskytov príslušného čísla v zozname. Súčasťou výstupu je legenda:
- dole – čísla položiek (0, 1, 2, …),
- vľavo – počty výskytov (výška stĺpcov),
- v oboch legendách sa vypisuje len každá piata hodnota (0, 5, 10, 15, …).
Očakávaný výstup pre zadaný zoznam values:
10 |
| |
| | |
| | | | |
| | | | | | |
5 | | | | | | | | | |
| | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |
0 5 10 15
2. Spustenie¶
alebo interaktívne v GHCi:
Výsledok treba vypisovať cez putStr, nie print. print na String vypíše úvodzovky a znaky nového riadku ako \n, takže by bol celý histogram v jednom riadku.
3. Základná myšlienka riešenia¶
Histogram je „obrázok“ zložený z textových riadkov, teda hodnota typu [String]. Riešenie ho skladá z troch blokov:
┌────┬──────────────────────────────────────┐
│ 10 │ | │
│ │ | | │ ← telo histogramu (drawRows)
│ .. │ ... │
│ │ | | | | | | | | | | | | | | | | | |│
├────┼──────────────────────────────────────┤
│ │ 0 5 10 15 │ ← spodná legenda (legendLine)
└────┴──────────────────────────────────────┘
↑
ľavá legenda (legendColumn)
- Telo – riadky so stĺpcami
|, od najvyššieho po najnižší. - Spodná legenda – jeden riadok s číslami položiek, ktorý sa pridá pod telo (
stacked). - Ľavá legenda – stĺpec s výškami, ktorý sa prilepí zľava k obom predchádzajúcim (
sideBySide).
Kľúčové pravidlo zarovnania: každá bunka má presne 2 znaky. Stĺpec histogramu je " |" alebo " ", bunka legendy je " 5", "10" alebo " ". Vďaka tomu všetko presne sedí pod sebou.
4. Prehľad funkcií¶
| Funkcia | Typ | Úloha |
|---|---|---|
histogram |
[Int] -> String |
hlavná funkcia, poskladá celý obrázok |
countOccurrences |
Ord a => [a] -> [(a, Int)] |
spočíta výskyty každého čísla |
mostFrequent |
Ord b => [(a, b)] -> (a, b) |
nájde dvojicu s najväčším počtom |
allOccurrences |
[Int] -> [(Int, Int)] |
výskyty pre všetky čísla 0..max (aj s nulou) |
drawRow |
Int -> [(Int, Int)] -> String |
jeden riadok tela histogramu |
drawRows |
Int -> [(Int, Int)] -> [String] |
všetky riadky tela (rekurzia) |
legendCell |
Int -> String |
jedna 2-znaková bunka legendy |
legendLine |
[(Int, Int)] -> String |
spodná legenda |
legendColumn |
Int -> [String] |
ľavá legenda |
alignRight |
Int -> String -> String |
zarovnanie textu doprava na danú šírku |
sideBySide |
[String] -> [String] -> [String] |
dva bloky vedľa seba |
stacked |
[String] -> [String] -> [String] |
dva bloky pod sebou |
Názvy funkcií sú rozdelené podľa toho, čo robia:
- počítanie –
countOccurrences,allOccurrences,mostFrequent, draw…– kreslenie tela histogramu (drawRow,drawRows),legend…– všetko, čo patrí k legende (legendCell,legendLine,legendColumn),- skladanie a formátovanie –
sideBySide,stacked,alignRight.
5. Podrobný popis kódu¶
5.1 Importy¶
Z Data.List sa používajú:
sort– zoradí zoznam,group– zoskupí za sebou idúce rovnaké prvky,maximumBy– nájde maximum podľa vlastnej porovnávacej funkcie.
Ostatné použité funkcie (map, concatMap, zipWith, replicate, lookup, maybe, id, unlines, …) sú v module Prelude, ktorý Haskell načíta automaticky, takže ich netreba importovať.
5.2 Vstupné dáta¶
Zoznam 88 čísel v rozsahu 0 až 18 zo zadania.
5.3 histogram – hlavná funkcia¶
histogram :: [Int] -> String
histogram numbers = unlines (legendC `sideBySide` (drawRows height occ `stacked` [legendL]))
where
occ = allOccurrences numbers
height = snd (mostFrequent occ)
legendL = legendLine occ
legendC = legendColumn height
V bloku where sa najprv pripravia pomocné hodnoty:
| Názov | Význam | Hodnota pre values |
|---|---|---|
occ |
dvojice (číslo, počet výskytov) pre čísla 0..18 |
[(0,1),(1,5),(2,3),…,(18,1)] |
height |
výška najvyššieho stĺpca | 10 (číslo 10 sa vyskytuje 10-krát) |
legendL |
spodný riadok legendy | " 0 5 10 15 " |
legendC |
ľavý stĺpec legendy (11 riadkov) | ["10"," "," "," "," "," 5"," ",…," "] |
Samotný výraz sa vyhodnocuje zvnútra von:
drawRows height occ– 10 riadkov tela histogramu,… `stacked` [legendL]– pod ne sa pridá riadok legendy, spolu 11 riadkov,legendC `sideBySide` …– ku každému z 11 riadkov sa zľava prilepí bunka ľavej legendy,unlines– zoznam riadkov sa spojí do jednéhoStringa za každý riadok sa pridá\n.
Spätné apostrofy (`sideBySide`) umožňujú zapísať dvojargumentovú funkciu medzi argumenty, ako operátor. Zápis a `sideBySide` b je to isté ako sideBySide a b.
5.4 countOccurrences – počítanie výskytov¶
countOccurrences :: Ord a => [a] -> [(a, Int)]
countOccurrences xs = map (\g -> (head g, length g)) (group (sort xs))
Funkcia funguje v troch krokoch. Príklad pre countOccurrences [3,1,3,2,3,1]:
sortzoradí čísla, takže rovnaké hodnoty sú vedľa seba:groupspojí susedné rovnaké prvky do podzoznamov:map (\g -> (head g, length g))z každej skupinygurobí dvojicu (prvý prvok skupiny, dĺžka skupiny):
\g -> … je lambda, teda anonymná funkcia bez mena, ktorá sa použije len na tomto mieste.
Obmedzenie Ord a => hovorí, že prvky musia byť porovnateľné, čo vyžaduje sort.
Poznámka: GHC 9.10 pri head vypíše varovanie -Wx-partial, lebo head [] by spôsobil chybu. Tu je však použitie bezpečné, pretože group nikdy nevytvorí prázdnu skupinu.
5.5 mostFrequent – najväčší počet¶
mostFrequent :: Ord b => [(a, b)] -> (a, b)
mostFrequent = maximumBy (\a b -> compare (snd a) (snd b))
maximumBy nájde najväčší prvok zoznamu podľa porovnávacej funkcie. Tá tu porovnáva druhé zložky dvojíc (snd), teda počty výskytov.
Pre values je výsledok (10, 10): číslo 10 sa vyskytuje 10-krát. V histogram sa z neho cez snd zoberie len počet, teda výška histogramu.
Funkcia je zapísaná bez argumentu (tzv. point-free štýl). maximumBy (…) je už funkcia, ktorá čaká na zoznam, takže ho netreba písať explicitne.
5.6 allOccurrences – výskyty aj pre chýbajúce čísla¶
allOccurrences :: [Int] -> [(Int, Int)]
allOccurrences xs = [(n, maybe 0 id (lookup n occ)) | n <- [0 .. maximum xs]]
where occ = countOccurrences xs
countOccurrences vracia dvojice len pre čísla, ktoré sa v zozname naozaj nachádzajú. Ak nejaké číslo chýba, histogram by preň nemal stĺpec a všetky ďalšie stĺpce by sa posunuli voči legende. Táto funkcia preto vytvorí dvojicu pre každé číslo od 0 po maximum.
Rozbor:
[ … | n <- [0 .. maximum xs]]– list comprehension, pre každénod 0 po najväčšie číslo vytvorí jeden prvok,lookup n occ– vyhľadánv zozname dvojíc a vrátiJust počet, ak tam je, aleboNothing, ak nie,maybe 0 id (…)– zJust početvyberiepočet, zNothingurobí0. FunkciamaybepriNothingvráti predvolenú hodnotu (0) a priJust xzavolá zadanú funkciu nax. Tu je toid(identita,id x = x), takže počet sa vráti bez zmeny.
Príklad:
Pre values sa v zozname nachádzajú všetky čísla 0 až 18, takže výsledok má 19 dvojíc a žiadnu nulu. Funkcia však zaručuje správnosť aj pre iné vstupy.
5.7 drawRow – jeden riadok tela¶
drawRow :: Int -> [(Int, Int)] -> String
drawRow target occ = concatMap cell occ
where cell (_, c) = if c >= target then " |" else " "
Vykreslí jeden vodorovný riadok histogramu vo výške target.
- Pomocná funkcia
celldostane dvojicu(číslo, počet). Číslo ignoruje (_) a pozerá sa len na početc: - ak
c >= target, stĺpec do tejto výšky siaha, nakreslí sa" |", - inak sa nakreslí prázdna bunka
" ". concatMap cell occpoužijecellna každú dvojicu a všetky výsledky spojí do jednéhoString.
Podmienka >= (nie ==) je dôležitá. Vďaka nej sa stĺpec vykreslí celý od spodu až po vrchol, nielen jeho najvyšší bod.
Príklad: drawRow 8 occ pre values (vo výške 8 siahajú len čísla 7, 9 a 10):
5.8 drawRows – všetky riadky tela (rekurzia)¶
drawRows :: Int -> [(Int, Int)] -> [String]
drawRows 0 _ = []
drawRows target occ = drawRow target occ : drawRows (target - 1) occ
Rekurzívne vytvorí riadky od výšky target smerom nadol:
- Základný prípad: pri výške
0už netreba nič kresliť, vráti sa prázdny zoznam. - Rekurzívny krok: vytvorí riadok vo výške
targeta pripojí ho (:) pred riadky odtarget - 1nižšie.
Postup pre height = 10:
drawRows 10 occ
= drawRow 10 occ : drawRows 9 occ
= drawRow 10 occ : drawRow 9 occ : drawRows 8 occ
= …
= drawRow 10 occ : drawRow 9 occ : … : drawRow 1 occ : []
Výsledkom je 10 riadkov, najvyšší je prvý. Pri výpise teda histogram „rastie“ zdola nahor.
5.9 legendCell – bunka legendy¶
legendCell :: Int -> String
legendCell target
| target `mod` 5 == 0 = alignRight 2 (show target)
| otherwise = " "
Vráti jednu 2-znakovú bunku legendy:
- ak je číslo deliteľné 5 (
modje zvyšok po delení), vypíše ho zarovnané doprava na 2 znaky, - inak vráti dve medzery.
Používajú sa tu stráže (guards): | uvádza podmienku a otherwise znamená „vo všetkých ostatných prípadoch“.
| Vstup | Výstup |
|---|---|
legendCell 0 |
" 0" |
legendCell 3 |
" " |
legendCell 5 |
" 5" |
legendCell 10 |
"10" |
Rovnaká funkcia slúži pre obe legendy, spodnú aj ľavú, lebo pravidlo „každá piata hodnota, šírka 2“ je v oboch rovnaké.
5.10 legendLine – spodná legenda¶
Pre každú dvojicu (číslo, počet) zoberie číslo (fst), urobí z neho bunku (legendCell) a všetky bunky spojí.
legendCell . fst je skladanie funkcií (operátor .): najprv sa použije fst, potom legendCell. Je to to isté ako \p -> legendCell (fst p).
Výsledok pre values (19 buniek po 2 znaky):
5.11 legendColumn – ľavá legenda¶
reverse [1..height]vytvorí výšky zhora nadol:[10, 9, …, 1],map legendCellz každej výšky urobí bunku:["10"," "," "," "," "," 5"," "," "," "," "],++ [" "]pridá na koniec ešte jednu prázdnu bunku, ktorá bude vedľa spodnej legendy.
Výsledok má teda height + 1 prvkov, presne toľko, koľko riadkov má telo spolu so spodnou legendou. To je potrebné, lebo sideBySide spája riadky po dvojiciach.
5.12 alignRight – zarovnanie doprava¶
alignRight :: Int -> String -> String
alignRight width str = replicate (width - length str) ' ' ++ str
Doplní reťazec zľava medzerami na požadovanú šírku. replicate n ' ' vytvorí n medzier.
5.13 sideBySide a stacked – skladanie blokov¶
sideBySide :: [String] -> [String] -> [String]
sideBySide left right = zipWith (++) left right
stacked :: [String] -> [String] -> [String]
stacked top bottom = top ++ bottom
Obe funkcie pracujú s „obrázkami“ typu [String], teda zoznamami riadkov.
stacked položí dva bloky pod seba, čo je obyčajné spojenie zoznamov:
sideBySide položí dva bloky vedľa seba. zipWith (++) spojí prvý riadok s prvým, druhý s druhým atď.:
Ak by bloky mali rôzny počet riadkov, zipWith by prebytočné riadky dlhšieho bloku zahodil. Preto legendColumn vracia presne height + 1 riadkov.
5.14 main¶
Vypíše nadpis a samotný histogram. putStr vypíše reťazec tak, ako je, a znaky \n z unlines spôsobia prechod na nový riadok.
6. Celý tok dát na menšom príklade¶
Vstup: histogram [1,3,3,5,5,5,5,5]
| Krok | Výsledok |
|---|---|
countOccurrences |
[(1,1), (3,2), (5,5)] |
allOccurrences |
[(0,0), (1,1), (2,0), (3,2), (4,0), (5,5)] |
height |
5 |
drawRows 5 occ |
5 riadkov tela |
legendLine occ |
" 0 5" |
legendColumn 5 |
[" 5"," "," "," "," "," "] |
Výstup:
Číslo 0, 2 a 4 sa vo vstupe nenachádzajú, majú prázdny stĺpec, a preto sa legenda neposunula. Práve na to slúži allOccurrences.
7. Použité koncepty Haskellu¶
| Koncept | Kde v kóde |
|---|---|
Funkcie vyššieho rádu (map, concatMap, zipWith, maximumBy) |
countOccurrences, drawRow, legendLine, sideBySide, … |
Lambda funkcie (\x -> …) |
countOccurrences, mostFrequent |
| List comprehension | allOccurrences |
| Rekurzia so základným prípadom | drawRows |
| Stráže (guards) | legendCell |
Pattern matching ((_, c)) |
drawRow |
Lokálne definície (where) |
histogram, allOccurrences, drawRow |
Skladanie funkcií (.) |
legendLine |
| Point-free štýl | mostFrequent |
Infixový zápis funkcií (`f`) |
histogram, legendCell |
Typ Maybe (lookup, maybe) |
allOccurrences |
Typové triedy (Ord) |
countOccurrences, mostFrequent |