Skip to content

← Späť

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


  1. Zadanie
  2. Spustenie
  3. Základná myšlienka riešenia
  4. Prehľad funkcií
  5. Podrobný popis kódu
  6. 5.1 Importy
  7. 5.2 Vstupné dáta – values
  8. 5.3 histogram – hlavná funkcia
  9. 5.4 countOccurrences – počítanie výskytov
  10. 5.5 mostFrequent – najväčší počet
  11. 5.6 allOccurrences – výskyty aj pre chýbajúce čísla
  12. 5.7 drawRow – jeden riadok tela
  13. 5.8 drawRows – všetky riadky tela (rekurzia)
  14. 5.9 legendCell – bunka legendy
  15. 5.10 legendLine – spodná legenda
  16. 5.11 legendColumn – ľavá legenda
  17. 5.12 alignRight – zarovnanie doprava
  18. 5.13 sideBySide a stacked – skladanie blokov
  19. 5.14 main
  20. Celý tok dát na menšom príklade
  21. 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:

  1. Spočítanie výskytov – sort + group zoskupí 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.
  2. Výška histogramu – najväčší počet výskytov nájdený cez maximumBy.
  3. Telo – rekurzívne drawRows vykreslí riadky zhora nadol. V každom riadku má stĺpec " |", ak siaha aspoň do tejto výšky, inak " ".
  4. Legendy – spodný riadok s číslami položiek a ľavý stĺpec s výškami, oba z rovnakej funkcie legendCell.
  5. Poskladanie – stacked dá legendu pod telo, sideBySide prilepí ľavú legendu, unlines z toho urobí jeden String.

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

runghc skurla_kamil_du4_histogram.hs

alebo interaktívne v GHCi:

ghci> :l skurla_kamil_du4_histogram.hs
ghci> putStr (histogram values)

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)
  1. Telo – riadky so stĺpcami |, od najvyššieho po najnižší.
  2. Spodná legenda – jeden riadok s číslami položiek, ktorý sa pridá pod telo (stacked).
  3. Ľ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

import Data.List (sort, group, maximumBy)

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

values :: [Int]
values = [6,2,12,10,7,3,0,12, ... ,1,8,11]

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:

  1. drawRows height occ – 10 riadkov tela histogramu,
  2. … `stacked` [legendL] – pod ne sa pridá riadok legendy, spolu 11 riadkov,
  3. legendC `sideBySide` … – ku každému z 11 riadkov sa zľava prilepí bunka ľavej legendy,
  4. unlines – zoznam riadkov sa spojí do jedného String a 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]:

  1. sort zoradí čísla, takže rovnaké hodnoty sú vedľa seba:
    [1,1,2,3,3,3]
    
  2. group spojí susedné rovnaké prvky do podzoznamov:
    [[1,1], [2], [3,3,3]]
    
  3. map (\g -> (head g, length g)) z každej skupiny g urobí dvojicu (prvý prvok skupiny, dĺžka skupiny):
    [(1,2), (2,1), (3,3)]
    

\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é n od 0 po najväčšie číslo vytvorí jeden prvok,
  • lookup n occ – vyhľadá n v zozname dvojíc a vráti Just počet, ak tam je, alebo Nothing, ak nie,
  • maybe 0 id (…) – z Just počet vyberie počet, z Nothing urobí 0. Funkcia maybe pri Nothing vráti predvolenú hodnotu (0) a pri Just x zavolá zadanú funkciu na x. Tu je to id (identita, id x = x), takže počet sa vráti bez zmeny.

Príklad:

countOccurrences [1,3,3]  =  [(1,1), (3,2)]
allOccurrences   [1,3,3]  =  [(0,0), (1,1), (2,0), (3,2)]

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 cell dostane dvojicu (číslo, počet). Číslo ignoruje (_) a pozerá sa len na počet c:
  • ak c >= target, stĺpec do tejto výšky siaha, nakreslí sa " |",
  • inak sa nakreslí prázdna bunka " ".
  • concatMap cell occ použije cell na každú dvojicu a všetky výsledky spojí do jedného String.

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 0 už netreba nič kresliť, vráti sa prázdny zoznam.
  • Rekurzívny krok: vytvorí riadok vo výške target a pripojí ho (:) pred riadky od target - 1 nižš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 (mod je 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

legendLine :: [(Int, Int)] -> String
legendLine occ = concatMap (legendCell . fst) occ

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):

" 0         5        10        15      "

5.11 legendColumn – ľavá legenda

legendColumn :: Int -> [String]
legendColumn height = map legendCell (reverse [1..height]) ++ ["  "]
  • reverse [1..height] vytvorí výšky zhora nadol: [10, 9, …, 1],
  • map legendCell z 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.

alignRight 2 "5"   = " 5"
alignRight 2 "10"  = "10"

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:

["AA",            ["CC"]          ["AA",
 "BB"]  `stacked`          =       "BB",
                                   "CC"]

sideBySide položí dva bloky vedľa seba. zipWith (++) spojí prvý riadok s prvým, druhý s druhým atď.:

["10",               [" |",          ["10 |",
 "  "]  `sideBySide`  " |"]    =      "   |"]

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

main :: IO ()
main = do
  putStrLn "---- histogram ----"
  putStr (histogram values)

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:

 5           |
             |
             |
         |   |
     |   |   |
   0         5

Čí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

Top