4. Haskelli 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-iga
nullid2 :: [Int] -> Int nullid2 xs = undefined
- funktsioonidega
sumjamap
nullid3 :: [Int] -> Int nullid3 xs = undefined
- funktsioonidega
lengthjafilter
nullid4 :: [Int] -> Int nullid4 xs = undefined
- listikomprehensiooniga
nullid5 :: [Int] -> Int nullid5 xs = undefined
Harjutusülesanded
Ülesanne 1
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!".
Ülesanne 2
Kirjuta listi pikkuse leidmise funktsioon kasutades foldl-i.
length' :: [a] -> Int length' = undefined
Ülesanne 3
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 4
Kirjuta listide konkateneerimise operatsioon kasutades foldr funktsiooni.
(Mitte kasutada sisseehitatud listide konkateneerimise operaatorit (++)!)
append' :: [a] -> [a] -> [a] append' xs ys = undefined
Ülesanne 5
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
Ülesanne 6
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: removeAll1 2 [2,0,1,3,2] = [0,1,3]
Lahenda ülesanne:
foldr-iga
removeAll1 :: Int -> [Int] -> [Int] removeAll1 n xs = undefined
- funktsiooniga
filter
removeAll2 :: Int -> [Int] -> [Int] removeAll2 n xs = undefined
- listikomprehensiooniga
removeAll3 :: Int -> [Int] -> [Int] removeAll3 n xs = undefined
Ülesanded*
fibs
Uuri standardfunktsioone zip ja zipWith. Seejärel proovi aru saada, kuidas järgnev defineerib lõpmatu Fibonacci arvude listi:
fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
primes
Proovi aru saada, kuidas järgnev defineerib lõpmatu algarvude listi:
primes :: [Integer]
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
arvud
Defineeri lõpmatu list arvud, mille elementideks on 0, 1, 2, 3 jne, kasutades map funktsiooni.
arvud :: [Integer] arvud = undefined
twinPrimes
Defineeri lõpmatu list twinPrimes, mille elementideks on algarvude paarid, kus teine algarv on täpselt kahe võrra suurem kui esimene, st (3,5), (5,7), (11, 13), (17,19) jne.
twinPrimes :: [(Integer, Integer)] twinPrimes = undefined
Kasuta ära ülaldefineeritud primes listi.
Rekursor foldr
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 (nimega 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