Funkcionálne programovanie

Zoznamy

Ciele

  1. Precvičiť si prácu s zoznamami v jazyku Haskell.
  2. Precvičiť používanie porovnávania vzorov (pattern matching).
  3. Precvičiť prácu s funkciami vyššieho rádu pre prácu s zoznamami.

Postup

Krok 1: Zoznamy

Základné operátory a funkcie pre prácu s zoznamami:

  • Konštruktory:
    • [] :: [a]
    • (:) :: a -> [a] -> [a]
  • Operátory:
    • (++) :: [a] -> [a] -> [a]
    • (!!) :: [a] -> Int -> a
  • Funkcie:
    • head :: [a] -> a
    • tail :: [a] -> [a]
    • last :: [a] -> a
    • init :: [a] -> [a]
    • length :: [a] -> Int
    • null :: [a] -> Bool
    • reverse :: [a] -> [a]
    • take :: Int -> [a] -> [a]
    • drop :: Int -> [a] -> [a]
    • elem :: Eq a => a -> [a] -> Bool

Úloha 1.1

Definujte funkciu rotateRight realizujúcu cyklický posun doprava o zadaný počet pozícií. Použite pritom len funkcie uvedené vyššie.

rotateRight :: Int -> [a] -> [a]

Príklady použitia:

rotateRight 2 [1, 2, 3, 4, 5] == [4, 5, 1, 2, 3]
rotateRight 3 "abcdef" == "defabc"
rotateRight 0 [1, 2, 3] == [1, 2, 3]

Krok 2: Porovnávanie vzorov

V niektorých prípadoch je možné definovať funkciu viacerými rovnicami, kde namiesto názvov parametrov budú uvedené vzory. Pri výbere rovnice, ktorá sa použije skutočné hodnoty parametrov sa postupne porovnávajú so vzormi až kým sa nenájde taký vzor, ktorý je možné s hodnotou stotožniť. Tento prístup sa nazýva pattern matching.

isOne 1 = True
isOne n = False

Úloha 2.1

Definujte funkciu myReplicate s dvoma parametrami: číslom a ľubovoľnou hodnotou. Funkcia vytvorí zoznam opakovaním hodnoty. Nepoužívajte pritom funkciu replicate zo štandardnej knižnice.

myReplicate :: Int -> a -> [a]

Príklady použitia:

myReplicate 4 8  == [8, 8, 8, 8]
myReplicate 3 'a' == "aaa"

Konštruktory dátovej štruktúry je možné použiť vo vzoroch na ľavej strane rovníc definujúcich funkcie:

mySum :: [Integer] -> Integer
mySum []     = 0
mySum (x:xs) = x + mySum xs

Úloha 2.2

Definujte funkciu count, ktorý spočíta vyskyty zadaného prvku v zozname. Použite porovnávanie vzorov a rekurziu.

count :: Eq a => a -> [a] -> Int

Príklad:

count 'r' "raspberry"

Úloha 2.3

Definujte funkciu compress, ktorá vytvorí zoznam, v ktorom budú vynechané duplicitné prvky idúce bezprostredne po sebe.

compress :: Eq a => [a] -> [a]

Príklad:

compress "aaabbbccdaa" == "abcda"

Úloha 2.4

Definujte funkciu merge, ktorá zlúči dva usporiadané zoznamy do jedného usporiadaného zoznamu.

merge :: Ord a => [a] -> [a] -> [a]

Príklad:

merge [1, 3, 6, 8, 9] [2, 4, 5, 7] == [1, 2, 3, 4, 5, 6, 7, 8, 9]

Krok 3: Funkcie vyššieho rádu pre prácu s zoznamami

Typické spôsoby manipulácie s zoznamami, ako je upravenie každého prvku, alebo výber časti prvkov na základe nejakého kritéria, sú realizované pomocou funkcií vyššieho rádu map a filter. Ich typové definície sú nasledovné:

map    :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]

Pokuste sa využiť tieto funkcie pri riešení nasledujúcich úloh.

Úloha 3.1

Definujte funkciu wordLengths, ktorá vráti zoznam dĺžok jednotlivých slov zozname.

wordLengths :: [String] -> [Int]

wordLengths ["functional", "programming", "is", "fun"] == [10, 11, 2, 3]

Úloha 3.2

Definujte funkciu inRange, ktorá vyberie zo zoznmu iba čísla v zadanom rozsahu (vrátane hraničných hodnôt).

inRange :: Int -> Int -> [Int] -> [Int]

inRange 3 7 [1,3,8,5,7,2] == [3,5,7]

Úloha 3.3

Definujte funkciu passingStudents, ktorá vyberie zo zoznamu študentov tých, ktorí získali viac ako 50 bodov. Každý študent je reprezentovaný dvojicou, kde prvý prvok je meno študenta a druhý počet bodov.

passingStudents :: [(String, Int)] -> [String]

passingStudents [("Eva",72), ("Adam",43), ("Mia",50), ("John",60)] == ["Eva","John"]

Úloha 3.4

Definujte funkciu normalizeNames, ktorá prevedie všetky mená na malé písmená a vynechá prázdne mená.

normalizeNames :: [String] -> [String]

normalizeNames ["Alice", "", "Bob"] == ["alice", "bob"]

Použite pritom aj funkciu toLower z modulu Data.Char, ktorý musíte importovať:

import Data.Char (toLower)

Úloha 3.5

Definujte funkciu getValue, ktorej prvým argumentom je zoznam tovarov. Tie sú reprezentované dvojicou. Prvý prvok dvojice je názov výrobcu a druhý hodnota konkrétneho tovaru. Jednotlivý výrobca môže byť v zozname viackrát. Vašou úlohou je vypočítať výslednú sumu za všetky tovary od výrobcu, ktorý je určený druhým parametrom.

products :: [(String, Int)]
products = [("avia",1000), ("trabant",500), ("avia",400), ("tatra",600),
            ("trabant",200), ("avia",700)]
getValue :: [(String, Int)] -> String -> Int
getValue products "trabant" == 700

Poznámka

Vo funkcii použite funkcie vyššieho rádu ako sú map a filter. Okrem toho môžete použiť funkciu sum, ktorá vypočíta súčet prvkov zoznamu čísel.

Úloha 3.6

Definujte funkciu replace, ktorá nahradí slova v texte podľa zadaného zoznamu náhrad. Funkcia má nahradzovať len celé slová, nie ich časti. Môžete pritom použiť zabudované funkcie words a unwords.

replace :: [(String, String)] -> String -> String

replacements = [("fox", "cat"), ("he", "she"), ("dog", "crocodile")]
sentence = "The quick brown fox jumps over the lazy dog"
replace replacements sentence == "The quick brown cat jumps over the lazy crocodile"

Zdroje

  1. Haskell – operations on lists
© Copyright 2026 KPI FEI TUKE