Cvičenie 2 – Zoznamy¶
Useful Files¶
Ciele¶
- Precvičiť si prácu s zoznamami v jazyku Haskell.
- Precvičiť používanie porovnávania vzorov (pattern matching).
- Precvičiť prácu s funkciami vyššieho rádu pre prácu s zoznamami.
Navigation¶
- Krok 1: Zoznamy
- Úloha 1.1 – rotateRight
- Krok 2: Porovnávanie vzorov
- Úloha 2.1 – myReplicate
- Úloha 2.2 – count
- Úloha 2.3 – compress
- Úloha 2.4 – merge
- Krok 3: Funkcie vyššieho rádu pre prácu s zoznamami
- Úloha 3.1 – wordLengths
- Úloha 3.2 – inRange
- Úloha 3.3 – passingStudents
- Úloha 3.4 – normalizeNames
- Úloha 3.5 – getValue
- Úloha 3.6 – replace
- Zdroje
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] -> atail :: [a] -> [a]last :: [a] -> ainit :: [a] -> [a]length :: [a] -> Intnull :: [a] -> Boolreverse :: [a] -> [a]take :: Int -> [a] -> [a]drop :: Int -> [a] -> [a]elem :: Eq a => a -> [a] -> Bool
Úloha 1.1 – rotateRight¶
Definujte funkciu rotateRight realizujúcu cyklický posun doprava o zadaný počet pozícií. Použite pritom len funkcie uvedené vyššie.
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]
rotateRight :: Int -> [a] -> [a]
rotateRight n xs = drop k xs ++ take k xs
where k = (length xs - n) `mod` length xs
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.
Úloha 2.1 – myReplicate¶
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.
Príklady použitia:
Konštruktory dátovej štruktúry je možné použiť vo vzoroch na ľavej strane rovníc definujúcich funkcie:
myReplicate :: Int -> a -> [a]
myReplicate 0 _ = []
myReplicate n x = x : myReplicate (n-1) x
-- alternatíva:
-- myReplicate n x = map (const x) [1..n]
Úloha 2.2 – count¶
Definujte funkciu count, ktorý spočíta vyskyty zadaného prvku v zozname. Použite porovnávanie vzorov a rekurziu.
Príklad:
count :: Eq a => a -> [a] -> Int
count _ [] = 0
count p (currentLetter:word)
| p == currentLetter = 1 + count p word
| otherwise = count p word
-- pomocou filter:
-- count e xs = length (filter (== e) xs)
-- pomocou map:
-- count e xs = sum (map (\x -> if x == e then 1 else 0) xs)
Úloha 2.3 – compress¶
Definujte funkciu compress, ktorá vytvorí zoznam, v ktorom budú vynechané duplicitné prvky idúce bezprostredne po sebe.
Príklad:
compress :: Eq a => [a] -> [a]
compress (x:y:xs)
| x == y = compress (y:xs)
| otherwise = x : compress (y:xs)
compress xs = xs
Úloha 2.4 – merge¶
Definujte funkciu merge, ktorá zlúči dva usporiadané zoznamy do jedného usporiadaného zoznamu.
Príklad:
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge l@(x:xs) r@(y:ys)
| x < y = x : merge xs r
| otherwise = y : merge l ys
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é:
Pokuste sa využiť tieto funkcie pri riešení nasledujúcich úloh.
Úloha 3.1 – wordLengths¶
Definujte funkciu wordLengths, ktorá vráti zoznam dĺžok jednotlivých slov zozname.
wordLengths :: [String] -> [Int]
wordLengths ws = map length ws
-- map length ["functional", "programming", "is", "fun"]
-- = [length "functional", length "programming", length "is", length "fun"]
-- = [10, 11, 2, 3]
-- point-free štýl (bez pomenovaného parametra ws):
-- wordLengths = map length
Úloha 3.2 – inRange¶
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 min max xs = filter isInRange xs
where
isInRange x = x >= min && x <= max
-- x=1: 1>=3 → False → vynechá
-- x=3: 3>=3 && 3<=7 → True → ponechá
-- x=8: 8>=3 && 8<=7 → False → vynechá
-- x=5: 5>=3 && 5<=7 → True → ponechá
-- x=7: 7>=3 && 7<=7 → True → ponechá
-- x=2: 2>=3 → False → vynechá
-- výsledok = [3,5,7]
Úloha 3.3 – passingStudents¶
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]
-- fst - vráti prvý prvok dvojice
passingStudents students = map fst (filter passing students)
where
passing (name, score) = score > 50
-- ("Eva",72): 72 > 50 → True → ponechá
-- ("Adam",43): 43 > 50 → False → vynechá
-- ("Mia",50): 50 > 50 → False (nie je ostro väčšie!) → vynechá
-- ("John",60): 60 > 50 → True → ponechá
-- = [("Eva",72), ("John",60)]
-- map fst [...] = ["Eva", "John"]
Úloha 3.4 – normalizeNames¶
Definujte funkciu normalizeNames, ktorá prevedie všetky mená na malé písmená a vynechá prázdne mená.
Použite pritom aj funkciu toLower z modulu Data.Char, ktorý musíte importovať:
normalizeNames :: [String] -> [String]
normalizeNames names = map (map toLower) (filter (not . null) names)
-- String = [Char], takže na prevod celého slova potrebujeme map toLower :: String -> String.
-- Keďže to chceme pre každé slovo v zozname, obalíme to ešte jedným map.
-- null "" vráti True, my chceme ponechať neprázdne mená, preto not . null.
Úloha 3.5 – getValue¶
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.
getValue :: [(String, Int)] -> String -> Int
getValue products manufacturer = sum (map snd matching)
where
matching = filter sameManufacturer products
sameManufacturer (name, _) = name == manufacturer
-- snd - vráti druhý prvok dvojice
-- filter ponechá len dvojice so zhodným výrobcom: [("trabant",500), ("trabant",200)]
-- map snd z nich vezme hodnoty: [500, 200]
-- sum [500, 200] = 700
Úloha 3.6 – replace¶
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"
replace :: [(String, String)] -> String -> String
replace replacements sentence = unwords (map replaceWord (words sentence))
where
replaceWord w = case lookup w replacements of
Just newWord -> newWord
Nothing -> w
-- words - rozdelí reťazec na zoznam slov (podľa bielych znakov)
-- unwords - spojí zoznam slov späť do reťazca (oddelené medzerami)
-- lookup - nájde kľúč v zozname dvojíc; vráti Just hodnota alebo Nothing
-- Nahrádzame celé slová, preto napr. "the" sa nezhoduje s "he".