Programming Languages 2020/21 fall

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 sum ja map

nullid3 :: [Int] -> Int
nullid3 xs = undefined

• funktsioonidega length ja filter

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