Kate Konczycki

Seznamy v Haskellu

Seznamy jsou v Haskellu poměrně důležitá struktura. Uvidíme, že se seznamy můžeme dělat mnoho užitečných operací. Nejprve si ukažme, jak si takový seznam můžeme pořídit.

Na rozdíl od seznamů v Prologu mají tyto seznamy určený typ. Tohoto typu pak musí být všechny položky seznamu.

Protože seznamy jsou spojové, můžeme použít nejzákladnější syntaxi pro seznamy, a to prostě zapsat seznam přímo pomocí operátoru (:) a konce seznamu []. Tato syntaxe lze též použít v Pattern Matchingu k tomu, abychom si seznam částečně rozbalili.

Tento zápis je samozřejmě otravný, tak můžeme seznam zapsat výčtem jeho prvků odděleným čárkami.

seznam1 = 3 : 1 : 4 : 1 : 5 : 9 : 2 : []
seznam2 = [3,1,4,1,5,9,2]

Další možností je vytvořit si jako seznam nějakou aritmetickou posloupnost. Pokud napíšeme [a..b], vytvoříme si tím seznam [a, a+1, ..., b]. Pokud bychom chtěli mít aritmetickou posloupnost s jiným krokem k, můžeme zapsat [a,a+k..b]. Pokud nespecifikujeme b, vytvoříme si nekonečný seznam.

> [1..10]
[1,2,3,4,5,6,7,8,9,10]

> [2,4..9]
[2,4,6,8]

> [0..]
-- vypisování donekonečna

Abychom mohli rozumně pracovat s nekonečným seznamem, můžeme si napsat funkci, která vrátí prvních k prvků. Líné vyhodnocování je zde zásadní, protože nebudeme zbytek seznamu potřebovat.

take :: Integer -> [a] -> [a]
take 0 _      = []
take _ []     = []
take k (x:xs)
  | k > 0     = x : (take (k-1) xs)
  | otherwise = error "Negative amount of elements???"

> take 3 [1..10]
[1,2,3]

> take 5 [2,4..]
[2,4,6,8,10]

> take 3 [0,0..]
[0,0,0]

Cvičení: Napište funkci drop :: Integer -> [a] -> [a], která naopak prvních k prvků zahodí.

Cvičení: Napište funkci takeWhile :: (a -> Bool) -> [a] -> [a]), která vrací nejdelší prefix seznamu takový, že pro všechny prvky toho platí podmínka f.

Cvičení: Napište funkci span :: (a -> Bool) -> [a] -> ([a],[a]), která bere predikát p a rozdělí seznam na prefix splňující p a zbytek seznamu, ve kterém první prvek již nesplňuje p.

Cvičení: Napište funkci group :: (a -> Bool) -> [a] -> [[a]], která vezme seznam a vrátí seznam souvislých podposloupností stejných prvků.

> drop 3 [1..5]
[4,5]

> takeWhile (<3) [1,2,3,2,1]
[1,2]

> span (<3) [1,2,3,2,1]
([1,2],[3,2,1])

> group [1,1,2,3,2,2,1,1,1]
[[1,1],[2],[3],[2,2],[1,1,1]]

Pokud bychom z nějakého důvodu nemohli nebo nechtěli použít Pattern matching k rozbalení seznamu, můžeme místo toho použít funkce head a tail, které respektive vrací hlavu a zbytek seznamu.

head (x:_) = x
tail (_:l) = l

> head (tail [1,3,4])
3

Cvičení: Napište funkci last :: [a] -> a, která pro konečný seznam vrátí jeho poslední prvek.

Též můžeme dva seznamy spojovat, k tomu máme k dispozici operátor (++) :: [a] -> [a] -> [a]. Časová složitost této funkce je lineární v délce prvního seznamu: musíme dojít jeho konec, než k němu můžeme připojit ten druhý. Díky línému vyhodnocování však nevadí, když je druhý seznam nekonečný.

> take 5 ([5,7,3] ++ [10..])
[5,7,3,10,11]

Filtrujeme, mapujeme, zipujeme...

Myšlenka nad prácí se seznamy ve funkcionálním programování spočívá v tom, že máme k dispozici obecné funkce, které pomocí jiných funkcí transformují seznamy. Velká část práce se seznamy lze pak provést skládáním těchto funkcí.

Jedna taková základní funkce je map, jenž aplikuje funkci na každý prvek seznamu. Tato funkce může změnit typ výsledného seznamu.

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x):(map f xs)

> map (\x -> x * 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]

> map (2*) [1..10]
[2,4,6,8,10,12,14,16,18,20]

> map (\x -> x `mod` 3 == 0) [1..10]
[False,False,True,False,False,True,False,False,True,False]

Cvičení: Napište funkci mocniny :: Integer -> [Integer], která vrátí nekonečný seznam mocnin celého čísla k.

Pokračujme dál. Nyní mějme nějakou funkci reprezentující predikát, tudíž vracející Bool. Pak máme nějaký seznam a chceme z něj zachovat pouze ty prvky, pro které predikát platí. Tuto operaci zachytíme funkcí filter.

filter :: (a -> Bool) -> [a] -> [a]
filter _ []   = []
filter p (x:xs)
  | p x       = x : ys
  | otherwise = ys
    where
        ys = filter p xs

Zde jsme použili syntaktickou konstrukci where, která umožňuje vytvořit novou proměnnou a pak specifikovat, co tato proměnná reprezentuje. Tím se můžeme vyhnout kopírování kódu. Podobně jako stráže, i tato konstrukce musí být odsazená.

Filtrování na rozdíl od takeWhile neumí pracovat s nekonečnými seznamy. Stále však díky línému vyhodnocování můžeme omezit rozsah filtrování.

> filter (<4) [3,1,4,1,5,9,2]
[3,1,1,2]

> filter (<10) [1..]
-- nikdy neskončí

> take 3 (filter (\x -> x `mod` 10 == 0) [1..])
[10,20,30]

Cvičení: Napište funkci slozene :: Integer -> Bool, která o přirozeném čísle řekne, zda je složené.

Cvičení: Napište funkci prvocisla :: [Integer], která vrátí seznam prvočísel. Může se hodit funkce not obracející výsledek Bool.

Tato funkce nám stačí k tomu, abychom mohli napsat třídění QuickSortem. Stačí, abychom vyfiltrovali prvky menší, než pivot a větší, než pivot, do dvou různých seznamů. Pak tyto dva seznamy prostě spojíme s pivotem ve správném pořadí.

sort :: Ord a => [a] -> [a] -- a je porovnatelný typ
sort []    = []
sort (p:l) = (sort lt) ++ p:(sort geq)
    where
        lt = filter (<p) l
        geq = filter (>=p) l

Cvičení: Vytvořte funkci toOrderedSet, která vezme seznam a vrátí seřazený seznam jeho unikátních prvků. Může se vám hodit group.

Podívejme se ještě na funkci zip. Pro její význam si představme, co dělá zip v realitě. V řeči seznamů to znamená, že máme dva seznamy a chceme z nich sestavit seznam dvojic. Délka seznamu dvojic bude odpovídat tomu kratšímu ze seznamů.

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

> zip [1..3] ['a','b','c']
[(1,'a'),(2,'b'),(3,'c')]

> zip [1..] ['a','b','c']
[(1,'a'),(2,'b'),(3,'c')]

Cvičení: Napište funkci unzip :: [(a,b)] -> ([a], [b]) dělající pravý opak funkce zip.

Často se však stává, že chceme dva seznamy spojit nějakou operací, třeba je sečíst po složkách. K tomuto účelu si napíšeme funkci zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]. Protože již máme všechny části skládačky k dispozici, stačí je poskládat dohromady.

-- Převod funkce dvou parametrů na funkci beroucí jednu dvojici
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (x,y) = f x y

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f as bs = map (uncurry f) (zip as bs)

> zipWith (+) [1..3] [10,20..]
[11,22,33]

Funkce uncurry se tak jmenuje, protože z víceparametrové funkce přes currying děláme "víceparametrovou" funkci, která potřebuje všechny parametry najednou (jako u procedurálních jazyků) jako jednu dvojici.

Cvičení: Napište funkci curry, která z funkce beroucí dvojici udělá funkci beroucí dva parametry.

Cvičení: Napište zipWith pomocí přímé rekurze.

Zaplatíme si za možnost nepoužití závorek

Aplikace funkce má vysokou prioritu. To je nám často na škodu, protože pak musíme psát závorky, pokud chceme skládat výrazy. Kdyby tak jen existovala možnost, jak se psaní mnoha závorek vyhnout...

Představme si operátor $. Co dělá? Podívejme se na jeho definici: f $ x = f x. Tedy $ je alternativní zápis aplikace. Může se zdát, že je zbytečný. Jeho užitečnost však spočívá ve velmi malé prioritě (menší, než běžná aplikace). Tudíž si "zaplatíme" to, že pak nemusíme používat závorky.

Ukažme si nyní nějaké příklady toho, jak může být $ užitečný. Postupně si ukážeme různé funkce bez a následně s tímto operátorem, abychom ten rozdíl viděli.

> take 5 ([5,7,3] ++ [10..])
[5,7,3,10,11]

> take 5 $ [5,7,3] ++ [10..]
[5,7,3,10,11]

> take 5 (map (*2) (tail [0..10]))
[2,4,6,8,10]

> take 5 $ map (*2) $ tail [0..10]
[2,4,6,8,10]

> head (tail (tail (tail (tail [1..10]))))
5

> head $ tail $ tail $ tail $ tail [1..10]
5

> map (\x -> negate (abs x)) [-3,-1,1,3]
[-3,-1,-1,-3]

> map (\x -> negate $ abs x) [-3,-1,1,3]
[-3,-1,-1,-3]

Jak vidíme, $ umí snadno nahradit závorky od dané chvíle až do konce výrazu. Není to však příme nahrazení závorek, protože je to stále alternativní zápis za aplikaci. Pozor na nesprávná použití:

> map ((+) 2) (tail [1..5])
[4,5,6,7]

> map ((+) 2) $ tail [1..5]
[4,5,6,7]

> map $ ((+) 2) $ tail [1..5]
error:
    • Couldn't match expected type ‘a -> b’
          with actual type ‘[Integer]’
    • In the second argument of ‘($)’, namely ‘(+) 2 $ tail [1 .. 5]’

> map $ ((+) 2) (tail [1..5])
error:
    • Couldn't match expected type ‘a -> b’
          with actual type ‘[Integer]’
    • Possible cause: ‘(+)’ is applied to too many arguments
      In the second argument of ‘($)’, namely ‘((+) 2) (tail [1 .. 5])’

Skládání funkcí

V Haskellu můžeme též funkce skládat v matematickém významu. Máme funkce f a g, a chceme, aby platilo f.g(x) = f(g(x)). Takové skládání můžeme zapsat přímočaře v Haskellu, dokonce existuje jako operátor (.).

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

Je důležité si všimnout, že tento operátor je asociativní zprava a vyhodnocování funkcí probíhá zprava doleva.

Z definice skládání vyplývá, že kdykoliv máme výraz tvaru f (g x), můžeme jej nahradit výrazem (f . g) x. Tím dostaneme krásný bonus. Skládání nyní nemusíme psát jako lambdu s explicitním parametrem. Ukažme si to znovu na příkladech:

> map (\x -> negate (abs x)) [-3,-1,1,3]
[-3,-1,-1,-3]

> map (\x -> (negate . abs) x) [-3,-1,1,3]
[-3,-1,-1,-3]

> map (negate . abs) [-3,-1,1,3]
[-3,-1,-1,-3]

Zde jsme jako argument mapu použili složení negate a abs. Původně jsme museli vytvořit novou lambdu reprezentující toto složení. Použitím (.) jsme se však dostali na výraz \x -> f x, což je prostě f.

Pomocí skládání funkcí pak můžeme alternativně zapsat zipWith.

zipWith f as bs = (map . uncurry) f $ zip as bs

Abychom pochopili, proč toto funguje, podívejme taktéž se postupně na typy.

(.) :: (b -> c) -> (a -> b) -> a -> c
map :: (u -> v) -> [u] -> [v]
-- b -> c | b = (u -> v), c = ([u] -> [v])
uncurry :: (k -> l -> m) -> ((k, l) -> m)
-- a -> b | a = (k -> l -> m), b = ((k, l) -> m)
-- u = (k, l), v = m

(map.uncurry) :: a -> c
(map.uncurry) :: (k -> l -> m) -> ([u] -> [v])
(map.uncurry) :: (k -> l -> m) -> ([(k, l)] -> [m])

Skládáním jsme vytvořili novou funkci, která očekává funkci o dvou parametrech a seznam dvojic. Funkci dáváme jako argument zipWith a seznam dvojic pak doplníme přes zip as bs.

Cvičení: Zkuste napsat toOrderedSet tak, že využívá jen skládání a částečnou aplikaci, tedy nemá žádné lambdy ani explicitní parametry.

Množinový zápis seznamu

Seznamy též můžeme tvořit pomocí množinového zápisu z jiných seznamů.

Mějme zápis tvaru {f(x) | x ∈ a, g(x)}. Tento zápis říká, že chceme všechny f(x) takové, že x je prvkem seznamu a a platí g(x). To je v Haskellu ekvivalentní zápisu [f x | x <- a, (g x) = 1].

Výhodou tohoto zápisu je, že můžeme specifikovat více proměnných z různých jiných seznamů. Takovým zápisem dostaneme kartézský součin.

> [2*x | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]

> [x + y | x <- [10,20,40], y <- [5,7]]
[15,17,25,27,45,47]

> [(x, y) | x <- [2..10], y <- [3,5], x `mod` y == 0]
[(3,3),(5,5),(6,3),(9,3),(10,5)]

Pokud používáme prvky pouze z jednoho zdrojového seznamu, je tento zápis v podstatě ekvivalentní složení funkcí map a filter.

Cvičení: Napište funkci vracející pro přirozené číslo k seznam všech pytagorejských trojic x, y, z: x² + y² = z², kde x ≤ y ≤ z ≤ k.