Viies Praktikum
Kõrgemat järku listifunktsioonid
Nagu Javas, on ka Haskellis disainimustrid, mis aitavad paremat koodi kirjutada ja koodist kiiremini aru saada. Kõige lihtsamad mustrid Haskellis on foldr, map ja foldl.
Selle asemel, et kirjutada
sumList :: [Int] -> Int sumList [] = 0 sumList (x:xs) = x + sumList xs
kirjutame hoopis
sumList :: [Int] -> Int sumList = foldr (+) 0
Kõige tähtsamad kõrgemat järku funktsioonid
-- foldr (#) a [x1, x2, ..., xn] = x1 # (x2 # (... # (xn # a))) foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ a [] = a foldr f a (x:xs) = f x (foldr f a xs) -- foldl (#) a [x1, x2, ..., xn] = (((a # x1) # x2) # ...) # xn foldl :: (b -> a -> b) -> b -> [a] -> b foldl _ a [] = a foldl f a (x:xs) = foldl f (f a x) xs -- map f [x1, x2, ..., xn] = [f x1, f x2, ..., f xn] map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs
Näiteülesanded
nullid
Kirjuta funktsioon, mis arvutab nullide arvu etteantud listis.
-- Näiteks: nullid1 [2,0,1,0,2] = 2
Lahenda ülesanne:
- lihtrekursiooniga
nullid1 :: [Int] -> Int nullid1 xs = undefined
- foldr-ga
nullid2 :: [Int] -> Int nullid2 xs = undefined
- funktsioonidega
sumjamap
nullid3 :: [Int] -> Int nullid3 xs = undefined
removeAll
Kirjuta kaheargumendiline funktsioon, mis võtab argumendiks arvu ja
arvude listi. Funktsioon peab tagastama listi, mis on saadud teisest argumendist kõigi esimese argumendi esinemiste ära jätmisel. Näiteks: removeAll 2 [2,0,1,3,2] = [0,1,3]
removeAll :: Int -> [Int] -> [Int] removeAll n = foldr undefined undefined
Redutseeri avaldis removeAll 2 [2,0,1,3,2].
upper
Kirjuta funktsioon, mis muudab sõne kõik tähed suurtähtedeks. (kasuta toUpper funktsiooni, milleks on vaja lisada import Data.Char)
-- upper "Tere!" == "TERE!" upper :: String -> String upper = undefined
Redutseeri avaldis upper "Tere!".
Harjutusülesanded
Ülesanne 1
Kirjuta listi pikkuse leidmise funktsioon kasutades foldl-i.
length' :: [a] -> Int length' = undefined
Ülesanne 2
Kasutades foldr, kirjuta funktsioon productList, mis tagastab listis olevate täisarvude korrutise. Funktsioon peab toimima ka lõpmatute listide korral, kui kuskil listi alguses leidub null.
-- Näide: -- productList [3,4,5] ==> 60 -- productList [80,79..] ==> 0 productList :: [Int] -> Int productList = undefined
Kas sellist funktsiooni saaks kirjutada kasutades foldl-i?
Redutseeri avaldis productList [3,2,0].
Ülesanne 3
Kirjuta listide konkateneerimise operatsioon kasutades foldr funktsiooni.
(Mitte kasutada sisseehitatud listide konkateneerimise operaatorit (++)!)
append' :: [a] -> [a] -> [a] append' xs ys = undefined
Ülesanne 4
Kasutades foldr, kirjuta funktsioon all, mis võtab argumendiks predikaadi ja listi.
Tagasta True ainult siis, kui kõik listi elemendid rahuldavad predikaati.
(Vihje: && on konjunktsiooni operaator)
-- Näiteks:
-- all isUpper "TERE!" == False -- kuna isUpper '!' == False
-- all isUpper "TERE" == True
-- ("TERE" == ['T','E','R','E'])
all :: (a -> Bool) -> [a] -> Bool all = undefined
Katsetamisel "Ambiguous occurrence" veateate vältimiseks on vaja lisada import Prelude hiding (all).
Ülesanne*
Andmetüüpide teooria ütleb, et foldr on listide rekursor, mis tähendab, et foldri kaudu saab defineerida kõik listifunktsioonid (kasutamata selleks rekursiooni).
Defineeri funktsioon foldl, kasutades foldri (ilma rekursioonita).
foldl_ :: (b -> a -> b) -> b -> [a] -> b foldl_ f a xs = undefined
Vihje: Foldr algväärtuseks võta identsusfunktsioon id ning foldl-i algväärtus a tuleb anda foldri neljandaks argumendiks. Nii saame foldr g id xs a === foldl f a xs võrrandid vastavalt listi pikkusele:
n=0: id a === a
n=1: g x1 id a === f x1 a
n=2: g x2 (g id x1) a === f x1 (f x2 a)
Nüüd jääb vaid tuletada sobilik g definitsioon, et võrdused kehtiks:
foldl_ :: (b -> a -> b) -> b -> [a] -> b foldl_ f a xs = foldr g id xs a where g x h b = undefined