Skip to content

← Späť na FP Labs

Cvičenie 2 – Zoznamy

Useful Files


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.
  1. Krok 1: Zoznamy
  2. Úloha 1.1 – rotateRight
  3. Krok 2: Porovnávanie vzorov
  4. Úloha 2.1 – myReplicate
  5. Úloha 2.2 – count
  6. Úloha 2.3 – compress
  7. Úloha 2.4 – merge
  8. Krok 3: Funkcie vyššieho rádu pre prácu s zoznamami
  9. Úloha 3.1 – wordLengths
  10. Úloha 3.2 – inRange
  11. Úloha 3.3 – passingStudents
  12. Úloha 3.4 – normalizeNames
  13. Úloha 3.5 – getValue
  14. Úloha 3.6 – replace
  15. 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] -> 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 – 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.

isOne 1 = True
isOne n = False

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

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
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 'r' "raspberry"
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 "aaabbbccdaa" == "abcda"
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 [1, 3, 6, 8, 9] [2, 4, 5, 7] == [1, 2, 3, 4, 5, 6, 7, 8, 9]
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é:

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 – wordLengths

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

wordLengths ["functional", "programming", "is", "fun"] == [10, 11, 2, 3]
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 3 7 [1,3,8,5,7,2] == [3,5,7]
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 [("Eva",72), ("Adam",43), ("Mia",50), ("John",60)] == ["Eva","John"]
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á.

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

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

import Data.Char (toLower)
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".

Zdroje

  1. Haskell – operations on lists

Top