Kõrgemat järku funktsioonid on funktsioonid, mis võtavad funktsioone argumentideks (näiteks tüübiga (A -> B) -> C) ja/või tagastavad funktsioone (näiteks tüübiga A -> (B -> C)). FP läbiv idee ongi, et funktsioonid on tavalised väärtused.
Seega on funktsionaalprogrammeerimises kõrgemat järku funktsioonide kasutamine tavaline nähtus. Kõik kahe ja enam parameetriga funktsioonid on Idrises rangelt võttes kõrgemat järku funktsioonid.
Kõrgemat järku funktsioonide kasutamisega kaasneb asjaolu, et funktsiooni parameetrite arv võib erineda funktsiooniväljakutse argumentide arvust. Programmi valiidsuse peab tagama tüübikontroll.
Kui argumente antakse liiga vähe, on tulemuseks funktsioon, mis ootab ülejäänud argumente. Näiteks (+) on kahe argumendiga funktsioon seega (+) 5 on ühe argumendiga funktsioon, mis võtab teise liidetava.
Kui argumente antakse rohkem kui parameetreid, lähevad ülejäänud argumendid funktsiooni poolt tagastatava funktsiooni argumendiks.
Näiteks võtame standardteegi funktsiooni const : a -> b -> a — kahe parameetriga funktsioon, mis on defineeritud kui const x y = x. Seega const ((+) 2) ((*) 2) 5 kutsub funktsiooni const välja kolme argumendiga kuigi parameetreid on kaks. Viimane argument 5 antakse edasi funktsioonile (+) 2 ja tulemus on 7.
|
Vaatame harjutamiseks mõningaid listidega seotud kõrgemat järku funktsioone. Idrise standardteegis on need funktsioonid natuke üldisemate tüüpidega — neid uurime täpsemalt liideste alampeatükis 10.3.
Funktsioon map võtab esimeseks parameetriks funktsiooni ja teiseks parameetriks listi ning rakendab funktsiooni kõigile listi elementidele ja tagagastab saadud tulemused listina.
Üks viis map-i defineerida on järgmine.
| 1map : (a -> b) -> List a -> List b 2map f [] = [] 3map f (x::xs) = f x :: map f xs |
Teine sobilik definitsioon oleks map f xs = [ f x | x <- xs ]. Aga meelde tuleks jätta hoopis järgmine võrdus pseudokoodis:
| map f [x1, x2, …, xn] = [f x1, f x2, …, f xn] |
Teine võimalik interpretatsioon map funktsioonile on, et map teisendab funktsiooni f : a -> b listide funktsiooniks map f : List a -> List b. Sellest interpretatsioonist saab map-i jaoks hiljem tuletada ka üldisema tüübi, mis tõstab teisendava funktsiooni iga sobiva konteineri teisenduse funktsiooniks.
Näiteks tahame ujukomaarvude listi konverteerida pöördarvude listiks. See vastab täpselt map-i mustrile. Seega saame defineerida järgmise funktsiooni.
| 1inverses : List Double -> List Double 2inverses = map (\ x => 1 / x) |
Kutsudes välja inverses [1,2,4,8], saame tulemuseks [1.0,0.5,0.25,0.125]. Samas paneme tähele, et definitsioonil pole ühtegi formaalset parameetrit ja map-le on antud kahest parameetrist vaid esimene.
Teine väga kasulik kõrgemat järku listifunktsioon on foldr, mis võtab parameetriteks listi töötlemise funktsiooni f, väärtuse b ja listi.
Funktsioon tagastab tühja listi puhul b ja kasutab mittetühja listi puhul funktsiooni f listi pea ja saba rekursiivsel väljakutsel.
Idrises saab funktsiooni defineerida järgnevalt.
| 1foldr : (a -> b -> b) -> b -> List a -> b 2foldr f b [] = b 3foldr f b (x::xs) = f x (foldr f b xs) |
Meelde võiks jätta järgmise võrduse, mis näitab, kuidas foldr listi elemente funktsiooniga (⊕) järjest vasakult-paremale töötleb. Täht r funktsiooni foldr lõpus tähistabki seda, et operatsiooni kasutatakse parem-assotsiatiivselt.
foldr (⊕) b [x1, x2, …, xn] = x1 ⊕ (x2 ⊕ (… ⊕ (xn ⊕ b))) |
Funktsiooni map saab defineerida läbi foldr-i järgnevalt.
| 1map : (a -> b) -> List a -> List b 2map f xs = foldr g [] xs 3 where g : a -> List b -> List b 4 g x ys = f x :: ys |
Nii saame tuletada foldr-i võrdusest map-i võrduse.
|
Funktsioon foldr on eriline rekursiooni operaator, mille tüübi ja implementatsiooni saab automaatselt (listi) andmetüübi deklaratsiooni järgi genereerida. Sisuliselt foldr asendab listis tühja listi konstruktori teise argumendiga ja mittetühja listi konstruktori esimese argumendiga.
Ehk foldr f b (x1 :: x2 :: … :: xn :: []) redutseerub samaks väärtuseks kui x1 `f` x2 `f` … `f` xn `f` b.
Teoreetiliselt saab listi rekursiooni operaatoriga defineerida kõik rekursiivsed listifunktsioonid ilma eksplitsiitselt rekursiooni kasutamata. Mõningal juhul on foldr-ga defineeritud funktsioon väga selge. Näiteks listi summa arvutamine.
| 1length : List a -> Nat 2length = foldr (+) 0 |
Funktsioonil foldr on teoreetiliselt väga head omadused, mis on seotud lõpmatute struktuuridega ja laisa väärtustamisega — uurime seda edasi peatükis 13. Kuna Idris on agar keel ja me töötleme kogu listi läbi, siis oleks parem kui fold-funktsioon oleks sabarekursiivne. Seega tuleks kaaluda hoopis funktsiooni foldl kasutamist.
Väga kasulik kõrgemat järku listifunktsioon on foldl, mis võtab parameetriteks listi töötlemise funktsiooni f, väärtuse b ja listi.
Funktsioon tagastab baasjuhul b. Mittetühja listi puhul kasutatakse rekursiooni, kus teiseks argumendiks võetakse funktsioon f rakendatud listi peale ja väärtusele b.
Idrises saab seda funktsiooni defineerida järgnevalt.
| 1foldl : (b -> a -> b) -> b -> List a -> b 2foldl f b [] = b 3foldl f b (x::xs) = foldl f (f x b) xs |
Meelde võiks jätta järgmise võrduse, mis näitab, kuidas foldl listi elemente funktsiooniga (⊕) järjest paremalt-vasakule töötleb. Täht l funktsiooni foldl lõpus tähistabki seda, et operatsiooni kasutatakse vasak-assotsiatiivselt.
foldl (⊕) b [x1, x2, …, xn] = ((((b ⊕ x1) ⊕ x2) ⊕ …) ⊕ xn) |
Suur erinevus foldr-i ja foldl-i vahel on see, et kuigi list läbitakse päripidises järjekorras siis lõpptulemus tuleb justkui tagurpidises järjekorras. Seetõttu saab foldl-iga väga lihtsalt implementeerida listi ümberpööramist. Vaata järgmist definitsiooni.
| 1reverse : List a -> List a 2reverse xs = foldl g [] xs 3 where g : List a -> a -> List a 4 g x y = y :: x |
Saame näidata foldl-i võrduse abil, kuidas reverse tõepoolest listi ümber pöörab.
|
Pöidlareegel on, et laiskades keeltes (nagu Haskell) peaks eelistama foldr funktsiooni, kuna see töötab ka lõpmatutel listidel. Agarates keeltes (nagu näiteks Scala või Idris) peaks võimalusel eelistama foldl-i.
Veel üks väga kasulik kõrgemat järku listifunktsioon on filter, mis võtab parameetriteks predikaadi f : a -> Bool ja listi xs : List a.
Funktsioon tagastab samas järjekorras listi xs elemendid, kus p tagastab true.
Idrises saab seda funktsiooni defineerida järgnevalt.
| 1filter : (a -> Bool) -> List a -> List a 2filter _ [] = [] 3filter p (x::xs) = if p x then x :: filter p xs else filter p xs |
Näiteks saame kasutada filter-it et jätta listis [1,20,3,40,5,60] alles kõik kümnest väiksemad arvud või kõik kümnest suuremad arvud. Funktsiooniks kasutame näiteks sektsioone < 10 ja > 10, kus binaarse operaatori puudu olevast vasakust poolest saab funktsiooni argument.
| Main> filter (< 10) [1,20,3,40,5,60] [1, 3, 5] Main> filter (> 10) [1,20,3,40,5,60] [20, 40, 60] |
Alternatiivne võimalus filter funktsiooni defineerimiseks oleks listikomprehensiooniga: filter p xs = [ x | x <- xs, p x ].
Vaikimisi imporditavas moodulis Prelude.Basics on veel mitmeid funktsioone, mida funktsionaalses koodis kasutada saaks. Näiteks funktsioonide komponeerimise operaatorit (.) saab kasutada teisenduste kombineerimiseks ilma argumenti nimetamata. Vaata järgnevat koodi.
| 1-- definitsioon standardteegis (lihtsustatult) 2-- infixr 9 . 3-- (.) : (b -> c) -> (a -> b) -> a -> c 4-- (.) f g = \x => f (g x) 5 6prodNonzero : List Integer -> Integer 7prodNonzero = product . filter (/= 0) |
Lisaks funktsioonide komponeerimisele on kasutusel ka $-operaator, mille abil saab vähendada sulgude kasutamist. Operaator rakendab teist (parempoolset) argumenti esimesele (vasakpoolsele) argumendile. Vaata järgnevat koodi.
Lisaks on FP gurudele tuntud funktsioonid, mis teisendavad kahe argumendiga funktsioonide ja paari funktsioonide vahel. Funktsioon curry võtab argumendiks funktsiooni tüübiga (a, b) -> c ja teisendab selle funktsiooniks tüübiga a -> b -> c. Vastupidise effektiga on uncurry : (a->b->c) -> (a, b) -> c, mis on kasulik olukordades, kus salvestame funktsiooni kaks argumenti paaridena ja tahame neid siis kasutada. Vaata järgnevat koodi.
| 1paarid : List (Int, Int) 2paarid = [(1,2), (3,4), (5,6)] 3 4arvutus : List Int 5arvutus = map (uncurry (*)) paarid |
filter' : (a -> Bool) -> List a -> List a, mis tagastab sisendi need elemendid, kus funktsioon tagastab true.
foldr, ning length . filter.
unzip' : List (a,b) -> (List a, List b) kasutades funktsiooni foldr: (elem -> acc -> acc) -> acc -> List elem -> acc.
reverse': List a -> List a kasutades funktsiooni foldl: (acc -> elem -> acc) -> acc -> List elem -> acc.
all': (a -> Bool) -> List a -> Bool, et kontrollida kas predikaat kehtib kõigil listi elementidel ilma eksplitsiitse tsüklita.
allEqual: List Int -> Bool, mis kontrollib kas kõik elemendid on omavahel võrdsed, ilma eksplitsiitse tsüklita.