Zoznamy

Ciele

  1. Precvičiť používanie porovnávania vzorov (pattern matching)
  2. Precvičiť prácu s funkciami vyššieho rádu pre prácu s zoznamami.
  3. Naučiť sa používať množinové abstrakcie (list comprehension).

Postup

Krok 1: Domáca úloha

Začiatok cvičenia budeme venovať diskusii k vypracovaným domácim úlohám z minulého cvičenia.

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.

myReplicate :: Int -> a -> [a]
myReplicate 4 8  == [8, 8, 8, 8]

Údajový typ zoznam má dva konštruktory:

  • [] — prázdny zoznam,
  • : — zoznam vzniknutý pridaním elementu do zoznamu.

Keďže to nie sú obyčajné funkcie, ale konštruktory dátovej štruktúry, je možné ich 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 sumFirstTwo, ktorá vypočíta súčet prvých dvoch čísel v zozname. Ak zoznam má iba jeden prvok, potom ten bude výsledkom funkcie. Ak je zoznam prázdny, nech je výsledkom hodnota 0.

sumFirstTwo :: [Integer] -> Integer
sumFirstTwo [1, 5, 2] == 6
sumFirstTwo [8] == 8
sumFirstTwo [] == 0

Krok 3: Rôzne spôsoby spracovania zoznamov

Okrem zabudovaných funkcií, rekurzie a porovnávania vzorov, máme k dispozícii aj ďalšie technike práce s zoznamami. Často používané sú funkcie vyššieho rádu ako map, filter, foldr, alebo foldl.

Operácie nad zoznamami je možne vyjadriť aj pomocou špeciálneho skráteného zápisu — množinovej abstrakcie (list comprehension). Jej tvár je nasledovný: [ výraz | generátory, filtre ]

Príklad definície triedenia algoritmom quick sort pomocou množinovej abstrakcie:

qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

Úloha 3.1

Definujte funkciu doubleAll :: [Integer] -> [Integer], ktorá vynásobí dvomi každý prvok zoznamu. Použite tri spôsoby implementácie:

  • pomocou rekurzie,
  • pomocou funkcie vyššieho rádu,
  • pomocou množinovej abstrakcie.

Úloha 3.2

Implementujte funkciu divisors, ktorej výsledkom je zoznam deliteľov kladného celého čísla:

divisors :: Integer -> [Integer]
divisors 12 == [1, 2, 3, 4, 6, 12]

Pomocou funkcie divisors definujte funkciu isPrime, ktorá určí, či číslo je prvočíslom (prvočísla sú deliteľné len číslom 1 a samým sebou).

isPrime :: Integer -> Bool

Zdroje

  1. The Fibonacci sequence - HaskellWiki
  2. Foldr Foldl Foldl' - HaskellWiki