IB015 Neimperativní programování Funkce na seznamech a Rekurze Jiří Barnat Libor Škarvada Jak si stojíme? Vím, že programovat znamená především přemýšlet ... o správném postupu, jak dojít k cíli, o dekompozici řešeného problému. Vím, že k obému mi pomáha především ... najít vhodný způsob uložení dat, správné otypování použitých artefaktů. Kudy dál? Musím se seznámit se základními stavebními kameny programovacího jazyka a naučit se je správně, efektivně a elegantně používat (Triforce). IB015 Neimperativní programování – 03 str. 2/36 Sekce Práce se seznamy v Haskellu (poprvé) IB015 Neimperativní programování – 03 str. 3/36 Funkce pro dekompozici seznamu První prvek seznamu head :: [a] -> a Seznam bez prvního prvku tail :: [a] -> [a] Poslední prvek seznamu last :: [a] -> a Seznam bez posledního prvku init :: [a] -> [a] head tail lastinit 1 2 3 4 5 6 IB015 Neimperativní programování – 03 str. 4/36 Demonstrační cvičení Z minula známe (:) , (++) Úkol 1 Zdvojte první prvek seznamu. Zduplikujte seznam a na konec přidejte první prvek. Úkol 2 Prohoďte první dva prvky seznamu. Prohoďte první a poslední prvek seznamu. IB015 Neimperativní programování – 03 str. 5/36 Další funkce pracující se seznamy 1 Zjištění počtu prvků v seznamu Vrací počet prvků v seznamu na nejvyšší úrovni, tj. nepočítá prvky v zanořených seznamech! length :: [a] -> Int Vyzkoušejte length [5,2,8] 3 length [] 0 length [[]] 1 length [[3],[8,4,5,5,5,4,5]] 2 IB015 Neimperativní programování – 03 str. 6/36 Další funkce pracující se seznamy 2 Prvních n prvků seznamu Vrátí prvních n prvků seznamu jako seznam take :: Int -> [a] -> [a] Seznam bez prvních n prvků seznamu Vrátí původní seznam bez prvních n prvků drop :: Int -> [a] -> [a] Získání n-tého prvku Vrátí prvek seznamu na dané pozici, první prvek je na pozici 0. (!!) :: [a] -> Int -> a IB015 Neimperativní programování – 03 str. 7/36 Další funkce pracující se seznamy 3 Seznam prvků v opačném pořadí reverse :: [a] -> [a] Aritmetické a logické funkce na seznamech minimum :: Ord a => [a] -> a maximum :: Ord a [a] -> a sum :: Num a => [a] -> a product :: Num a => [a] -> a or :: [Bool] -> Bool and :: [Bool] -> Bool Srovnejte s binárními funkcemi min :: Ord a => a -> a -> a max :: Ord a => a -> a -> a (&&) :: Bool -> Bool -> Bool (||) :: Bool -> Bool -> Bool IB015 Neimperativní programování – 03 str. 8/36 Demonstrační cvičení Úkol 3 Rozhodněte, zda je seznam palindrom. Úkol 4 Na neprázdných seznamech typu Num a => [a] definujte funkci, která rozhodne, zda je součet prvků seznamu větší, než součin. IB015 Neimperativní programování – 03 str. 9/36 Další funkce pracující se seznamy 4 Aplikace funkce na prvky v seznamu map :: (a -> b) -> [a] -> [b] Vyzkoušejte map not [True,False,False] ∗ [False,True,True] let f x = x + 1 in map f [4,5,6] ∗ [5,6,7] map even [3,4,5] ∗ [False,True,False] IB015 Neimperativní programování – 03 str. 10/36 Další funkce pracující se seznamy 5 Výběr prvků seznamu podle dané podmínky filter :: (a -> Bool) -> [a] -> [a] Vyzkoušejte filter odd [1,2,3] ∗ [1,3] filter (not.odd) [1,2,3] ∗ [2] Všimněte si Funkce map i filter berou jako své argumenty jiné funkce. Takovým funkcím říkáme funkce vyšších řádů. IB015 Neimperativní programování – 03 str. 11/36 Demonstrační cvičení Úkol 5 Rozhodněte, zda je seznam typu Integral a => [a] tvořen pouze sudými čísly. Úkol 6 Definujte funkci, která vrátí délku zadaného seznamu, tak, abyste nepoužili funkci length . Úkol 7 Pro seznam dvojic, zaměňte první složku každé dvojice za druhou a naopak. Funkci definujte s použitím klíčového slova where . Poznámka: where se podobně jako let ... in používá pro lokální definice s tím, že klauzule where se vyskytuje až za hlavním výrazem. IB015 Neimperativní programování – 03 str. 12/36 Další funkce pracující se seznamy 6 Ponechání/odstranění podmínkou definovaného prefixu První prvek od začátku seznamu nevyhovující zadané podmínce definuje místo, kde končí vracený, nebo zahozený prefix. takeWhile :: (a -> Bool) -> [a] -> [a] dropWhile :: (a -> Bool) -> [a] -> [a] Vyzkoušejte takeWhile odd [1,3,5,6,7,8,9] ∗ [1,3,5] dropWhile odd [1,3,5,6,7,8,9] ∗ [6,7,8,9] IB015 Neimperativní programování – 03 str. 13/36 Další funkce pracující se seznamy 7 Spojení seznamu seznamů do jednoho seznamu concat :: [[a]] -> [a] Spojení dvou seznamů do seznamu dvojic zip :: [a] -> [b] -> [(a,b)] Délka výsledného seznamu je definována kratším ze dvou zadaných seznamů. Vyzkoušejte concat [[1,2],[2,3],[3,4]] ∗ [1,2,2,3,3,4] zip [1,2,3,4] "abc" ∗ [(1,’a’),(2,’b’),(3,’c’)] IB015 Neimperativní programování – 03 str. 14/36 Další funkce pracující se seznamy 8 Spojení seznamu pomocí funkce zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] Vyzkoušejte zipWith (+) [1,2,3] [1,2,3,4,5] ∗ [2,4,6] zipWith take [1,2,3] ["aaa","bbb","ccc"] ∗ ["a","bb","ccc"] IB015 Neimperativní programování – 03 str. 15/36 Trocha softwarové archeologie Úkol Co počítá funkce fn a jakého je typu? fn s = and (map f (zip s (head s:s))) where f (a,b) = a >= b Řešení IB015 Neimperativní programování – 03 str. 16/36 Trocha softwarové archeologie Úkol Co počítá funkce fn a jakého je typu? fn s = and (map f (zip s (head s:s))) where f (a,b) = a >= b Řešení fn :: Ord a => [a] -> Bool Funkce fn pro zadaný seznam rozhodne, zda je seznam neklesající. IB015 Neimperativní programování – 03 str. 16/36 Nesplnitelný úkol Zadání S využitím stávajících znalostí o programovacím jazyce Haskell naprogramujte funkci len , která spočítá délku seznamu, a to tak, aniž byste použili funkci length , sum či jinou podobnou funkci. Náznak řešení len [] = 0 len (_:[]) = 1 len (_:_:[]) = 2 len (_:_:_:[]) = 3 len (_:_:_:_:[]) = 4 ... IB015 Neimperativní programování – 03 str. 17/36 Sekce Rekurze IB015 Neimperativní programování – 03 str. 18/36 Rekurze Co je to rekurze Definice funkce, nebo datové struktury, s využitím sebe sama. Význam v programování Umožňuje konečně dlouhý zápis definice funkce, která je definována pro nekonečně mnoho strukturálně odlišných parametrů. Příklad Funkci length , která při aplikaci na seznam vrací jeho délku, je nutné definovat rekurzivně. length :: [a] -> Int length [] = 0 length (_:s) = 1 + length s IB015 Neimperativní programování – 03 str. 19/36 Příklad výpočtu rekurzivní definice length :: [a] -> Int length [] = 0 length (_:s) = 1 + length s length [6,7,8,9] 1 + length [7,8,9] 1 + ( 1 + length [8,9]) 1 + ( 1 + ( 1 + length [9])) 1 + ( 1 + ( 1 + ( 1 + length []))) 1 + ( 1 + ( 1 + ( 1 + 0 ))) 1 + ( 1 + ( 1 + 1 )) 1 + ( 1 + 2 ) 1 + 3 4 IB015 Neimperativní programování – 03 str. 20/36 Rekurze na číselných funkcích factorial :: Integer -> Integer factorial 0 = 1 factorial x = x * factorial (x-1) factorial 4 4 * factorial (4-1) 4 * factorial (3) 4 * ( 3 * factorial (3-1)) 4 * ( 3 * factorial (2)) 4 * ( 3 * ( 2 * factorial (2-1))) 4 * ( 3 * ( 2 * factorial (1))) 4 * ( 3 * ( 2 * ( 1 * factorial (0)))) 4 * ( 3 * ( 2 * ( 1 * 1 ))) 4 * ( 3 * ( 2 * 1 )) 4 * ( 3 * 2 ) 4 * 6 24 IB015 Neimperativní programování – 03 str. 21/36 Sekce Práce se seznamy v Haskellu (podruhé) IB015 Neimperativní programování – 03 str. 22/36 head, tail, init, last První prvek seznamu head :: [a] -> a head (x:_) = x Seznam bez prvního prvku tail :: [a] -> [a] tail (_:s) = s Poslední prvek seznamu last :: [a] -> a last (x:[]) = x last (_:s) = last s Seznam bez posledního prvku init :: [a] -> [a] init (_:[]) = [] init (x:_:[]) = [x] init (x:s) = x:init s head tail lastinit 1 2 3 4 5 6 IB015 Neimperativní programování – 03 str. 23/36 null, length, (!!) Test na prázdný seznam null :: [a] -> Bool null (_:_) = False null [] = True Délka seznamu length :: [a] -> Int length [] = 0 length (_:s) = 1 + length s N-tý prvek seznamu (!!) :: [a] -> Int -> a (x:_) !! 0 = x (_:s) !! k = s !! (k-1) IB015 Neimperativní programování – 03 str. 24/36 take, drop Prvních n prvků seznamu take :: Int -> [a] -> [a] take _ [] = [] take n (x:s) = if (n>0) then x : take (n-1) s else [] Seznam bez prvních n prvků; drop :: Int -> [a] -> [a] drop _ [] = [] drop n (x:s) = if (n>0) then drop (n-1) s else (x:s) Poznámka Při infixovém použití binární funkce klesá její priorita! x : take (n-1) s = x : (take (n-1) s) IB015 Neimperativní programování – 03 str. 25/36 concat, filtr, replicate Spojení seznamů v seznamu concat :: [[a]] -> [a] concat [] = [] concat (x:s) = x ++ concat s Vynechání prvků nesplňujících danou podmínku filter :: (a -> Bool) -> [a] -> [a] filter _ [] = [] filter f (x:s) = if (f x) then x : filter f s else filter f s Vytvoření seznamu n-násobným kopírováním daného prvku replicate :: Int -> a -> [a] replicate 0 _ = [] replicate k x = x : replicate (k-1) x IB015 Neimperativní programování – 03 str. 26/36 takeWhile, dropWhile, map Vynechání prvků seznamu od prvního, který nesplňuje podmínku takeWhile :: (a->Bool) -> [a] -> [a] takeWhile _ [] = [] takeWhile p (x:s) = if (p x) then x : takeWhile p s else [] Vynechání prvků seznamu po první, který nesplňuje podmínku dropWhile :: (a->Bool) -> [a] -> [a] dropWhile _ [] = [] dropWhile p (x:s) = if (p x) then dropWhile p s else x:s Aplikace funkce na všechny prvky seznamu map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:s) = f x : map f s IB015 Neimperativní programování – 03 str. 27/36 zip,unzip Spojení dvou seznamů do seznamu uspořádaných dvojic zip :: [a] -> [b] -> [(a,b)] zip [] _ = [] zip _ [] = [] zip (x:s) (y:t) = (x,y) : zip s t Rozdělení seznamu dvojic na dvojici seznamů unzip :: [(a,b)] -> ([a],[b]) unzip [] = ([],[]) unzip ((x,y):s) = (x : fst t, y : snd t) where t = unzip s IB015 Neimperativní programování – 03 str. 28/36 zipWith Výpočet aplikace binární funkce na seznamy argumentů zipWith :: (a->b->c)->[a]->[b]->[c] zipWith _ _ [] = [] zipWith _ [] _ = [] zipWith f (x:s) (y:t) = f x y : zipWith f s t Pozorování zip = zipWith (,) IB015 Neimperativní programování – 03 str. 29/36 Sekce Demonstrace řešení vybraných příkladů (mentálně náročné) IB015 Neimperativní programování – 03 str. 30/36 Rekurzivní dělení dvojkou Kolikátá mocnina dvojky Napište funkci, která zjistí, kolikrát se vyskytuje dvojka v prvočíselném rozkladu zadaného celého čísla. Řešení Myšlenka: kolikrát mohu bezezbytku podělit dvojkou. kolik2 :: (Integral a, Integral b) => a -> b kolik2 x = y where (y,_) = f_aux (0,x) f_aux (cnt, rem) = if (rem<2) || (rem ‘mod‘ 2 /= 0) then (cnt,rem) else f_aux (cnt+1, rem ‘div‘ 2) IB015 Neimperativní programování – 03 str. 31/36 Zatřizování seřazených seznamů (merge) Zatřízení sezařených seznamů Napište funkci, která pro dva seřazené seznamy vrátí jeden seřazený seznam, který obsahuje všechny prvky z původních dvou seznamů, tj. zatřídí dva seznamy „do sebe“. Řešení merge [] x = x merge x [] = x merge (x:xs) (y:ys) = if x [KousekDortu] dort s = if (length s >= 8) then s else dort (map (/2) s ++ map (/2) s) IB015 Neimperativní programování – 03 str. 34/36 Checkpoint Úkol 1 Mějme konečný seznam celých čísel. Napište funkci, která vynásobí všechna čísla v seznamu zadaným parametrem, a pak ze seznamu ponechá pouze čísla dělitelná číslem 7. Funkci upravte tak, aby výše zmíněné číslo 7 nebylo fixně v kódu funkce, ale byl to její další parametr. Úkol 2 Napište funkci, která o seznamu řetězců rozhodne, zda tento seznam obsahuje alespoň 4 řetězce délky minimálně 2. Funkci upravte tak, aby výše zmíněné čísla 4 a 2 nebyla fixně v kódu funkce, ale byly to její další parametry. IB015 Neimperativní programování – 03 str. 35/36 Challenge Challenge 1 Napište program, který pomocí principu rekurze a s využitím odpřednášených operací na seznamech vypočítá seznam obsahující čísla od 1 do 1024. Snažte se o to, aby hloubka rekurze byla co nejmenší (logaritmická). Challenge 2 Jsou-li vám známy cykly s pevným počtem opakování z nějakého imperativního programovacího jazyka, popřemýšlejte o obecném postupu, jak nahradit tyto cykly voláním rekurzivní funkce. IB015 Neimperativní programování – 03 str. 36/36