Functional Programming 2023/24 fall

Kodutöö 3

Kõrgemat järku listifunktsioonid

Nagu Javas, on ka Idrises disainimustrid, mis aitavad paremat koodi kirjutada ja koodist kiiremini aru saada. Kõige lihtsamad mustrid Idrises on foldr, map ja foldl.

Selle asemel, et kirjutada

sumList : List Int -> Int
sumList []     = 0
sumList (x :: xs) = x + sumList xs

kirjutame hoopis

sumList : List 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 -> List 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 -> List 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) -> List a -> List b
 map _ []        = []
 map f (x :: xs) = f x :: map f xs

Konspekt

Lisalugemine (vabatahtlik):

Type-Driven development with Idris peatükid:

• Chapter 2. Getting started with Idris, alampeatükid:
  • 2.2. Functions: the building blocks of Idris programs, alampeatükid:
    • 2.2.5. Higher-order function types
    • 2.2.6. Anonymous functions

Praktikumi ja kodutöö ülesanded

Tagasiside

Alates sellest praktikumist palume anda tagasisidet kodutöö mahu kohta koos kodutööga. Võib kirjutada tervele kodutööle kulunud aja või iga ülesande kohta eraldi või mingi kombinatsioon nendest. Kirjutage, kui mingi ülesanne võtab ebamõistlikult palju aega.

1. Funktsioon filter' (standardteegis filter moodulis Data.List)

Kirjuta funktsioon filter', mis tagastab etteantud listi kõik need elemendid millel esimese argumendina antud funktsioon tagastab True.

Näiteks: filter' (<3) [3,0,1,3,2,3] == [0,1,2].

filter' : (a -> Bool) -> List a -> List a
filter' = ?rhs_filter1

2. Funktsioon nullid

Kirjuta funktsioon, mis arvutab nullide arvu etteantud listis. Näiteks: nullid1 [2,0,1,0,2] = 2.

Lahenda ülesanne:

• lihtrekursiooniga

nullid1 : List Int -> Int
nullid1 xs = ?rhs_nullid1

• foldr-iga

nullid2 : List Int -> Int
nullid2 xs = ?rhs_nullid2

• funktsioonidega sum ja map

nullid3 : List Int -> Int
nullid3 xs = ?rhs_nullid3

• funktsioonidega length ja filter'

nullid4 : List Int -> Nat
nullid4 xs = ?rhs_nullid4

• listikomprehensiooniga ja funktsioonidega sum või length

nullid5 : List Int -> Int
nullid5 xs = ?rhs_nullid5

3. Funktsioon length'

Kirjuta listi pikkuse leidmise funktsioon kasutades foldl-i.

length' : List a -> Int
length' = ?rhs_length

4. Funktsioon productList

Kasutades foldr, kirjuta funktsioon productList, mis tagastab listis olevate täisarvude korrutise.

productList : List Int -> Int
productList = ?rhs_productList 

Näiteks

productList []         ==> 1
productList [3,4,5]    ==> 60

Redutseeri avaldis productList [3,2,0].

5. Funktsioon append'

Kirjuta listide konkateneerimise operatsioon kasutades foldr funktsiooni. (Mitte kasutada sisseehitatud listide konkateneerimise operaatorit (++)!)

append' : List a -> List a -> List a
append' xs ys = ?rhs_append'

6. Funktsioon all'

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)

isEven : Nat -> Bool
isEven Z         = True
isEven (S Z)     = False
isEven (S (S n)) = isEven n

all' : (a -> Bool) -> List a -> Bool
all' = ?rhs_all'

Näiteks:

all' isEven [1, 2, 3] == False
all' isEven [2, 4, 6] == True

7. Funktsioon reverse'

Kirjuta listi ümberpööramise funktsioon reverse', kasutades foldl-i.

reverse' : List a -> List a
reverse' = foldl rev df
  where
    df : List a
    df = ?rhs_df_rev
    rev : List a -> a -> List a
    rev x y = ?rhs_rev

Näiteks:

reverse' [] ==> []
reverse' [1,2,3] ==> [3,2,1]

8. Funktsioon eemaldaNullid

Kirjuta foldr-ga funktsioon eemaldaNullid, mis eemaldab listist kõik nullid. Teised listi elemendid peavad jääma samasse järjekorda.

eemaldaNullid : List Int -> List Int
eemaldaNullid = foldr rem df
  where
    df : List Int
    df = ?rhs_df_rem
    rem : Int -> List Int -> List Int
    rem x y = ?rhs_rem

Näiteks:

eemaldaNullid []           ==> []
eemaldaNullid [1,0,1,0,2]  ==> [1,1,2]
eemaldaNullid [1,1,0,0,2]  ==> [1,1,2]
eemaldaNullid [0,0,0,6,0]  ==> [6]

9. Funktsioon allEqual

Kasutades mõnda kõrgemat järku funktsiooni (nt foldr), kirjuta funktsioon allEqual, mis kontrollib, kas täisarvude listi kõik elemendid on võrdsed.

allEqual : List Int -> Bool
allEqual xs = ?rhs_allEqual

Näiteks:

allEqual []      ==> True
allEqual [1,2]   ==> False
allEqual [1,1,1] ==> True
allEqual [1,2,1] ==> False

10. Funktsioon unzip'

Kasutades funktsiooni foldr, kirjuta funktsioon unzip', mis jagab paaride listi kaheks eraldi listiks.

unzip' : List (a, b) -> (List a, List b)
unzip' = foldr f z
  where
    z : (List a, List b)
    z = ?rhs_z
    f : (a, b) -> (List a, List b) -> (List a, List b)
    f = ?rhs_f

Näiteks:

unzip' [(1,'x'), (4,'1'), (2,'p')] == ([1, 4, 2], ['x', '1', 'p'])
unzip' [] == ([], [])

Lisaülesanded

11. Funktsioon 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: removeAll1 2 [2,0,1,3,2] = [0,1,3]

Lahenda ülesanne:

• foldr-iga

removeAll1 : Int -> List Int -> List Int
removeAll1 n xs = ?rhs_removeAll1

• funktsiooniga filter

removeAll2 : Int -> List Int -> List Int
removeAll2 n xs = ?rhs_removeAll2

• listikomprehensiooniga

removeAll3 : Int -> List Int -> List Int
removeAll3 n xs = ?rhs_removeAll3

12. Funktsioon any'

Kasutades foldr-i, kirjuta funktsioon any', mis võtab argumendiks predikaadi ja listi. Tagasta True ainult siis, kui leidub listi element, mis rahuldab predikaati. (Vihje: || on disjunktsiooni operaator)

any' : (a -> Bool) -> List a -> Bool
any' p xs = ?rhs_any'

Näiteks:

any' isUpper ['T', 'e', 'r', 'e', '!'] ==> True   -- kuna isUpper 'T' == True
any' isUpper ['t', 'e', 'r', 'E', '!'] ==> True   -- kuna isUpper 'E' == True
any' isUpper ['t', 'e', 'r', 'e', '!'] ==> False

Tärnülesanded

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 -> List a -> b
foldl_ f a xs = ?rhs_foldl_

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 -> List a -> b
foldl_ f a xs = foldr ?g id xs a