Olukorda, kus sama sümbol tähistab mitut erinevat tüüpi väärtusi nimetatakse programmeerimiskeeltes polümorfismiks. Näiteks 5 võib tähistada täisarvu Int kui ka ujukomaarvu Double.
Polümorfisme on mitut erinevat sorti. Näiteks võib polümorfismiks nimetada alamtüüpimist, parameetrilist polümorfismi ja ad-hoc polümorfismi. Järgnevalt arutleme erinevate polümorfismi sortide üle ja vaatame, mis on funktsionaalprogrammeerimises relevantne.
Programmeerimiskeeles Java on List<String> tüübi Collection<String> alamtüüp. Seega iga sõnede list on ka sõnede kollektsioon ja sama sõnede list on ühes kontekstis list ja teises kollektsioon.
Funktsionaalprogrammeerimises on alamtüüpimine enamasti seotud kirjete tüübiga, kus tüübiks ei ole kirje nimi vaid kirje signatuur. Idrises kirjete alamtüüpimist ei ole — kirje tüübid on vaja eraldi defineerida ning anda definitsioonile nimi. Seega vaatame keelt OCaml, kus tüüp {x: int, y: int} on tüübi {x: int, y: int, z: int} alamtüüp ehk {x: int, y: int} <: {x: int, y: int, z: int}. Funktsioonile, mis võtab parameetriks kahe väljaga kirje, võib argumendiks anda ka rohkemate väljadega kirje.
Vajadus alamtüüpimise järele sõltub programmeerimiskeeles kasutavatest mustritest. Mõningatel juhtudel võib sama efekti, näiteks et 5 on nii Int kui Double, saavutada nii alamtüüpimise kui ka näiteks ad-hoc polümorfismi kasutades.
Parameetriline polümorfism võimaldab sama koodi rakendada sõltumata andmete konkreetsest tüübist. Üks lihtsaim parameetrilise polümorfismi näide on identsusfunktsioon id : a -> a, mis tagastab sisendi olenemata tüübist.
Paramteetrilist polümorfismi tunneb Idrises ära selle järgi, et tüübis on kasutatud implitiitseid tüübimuutujaid. Näiteks map : (a -> b) -> List a -> List b on polümorfne funktsioon. Kui öeldakse polümorfne funktsioon, siis mõeldaksegi enamasti parameetrilist polümorfismi.
Funktsioonile map saab rakendada suvalist tüüpi funktsiooni ning tulemuseks on vastav listide teisendusfunktsioon.
Idrises on sisuliselt kaks võimalust luua tüübiparameetrit. Esiteks juba nähtud implitsiitne võimalus, kus kasutatakse mingit uut muutujanime. Näiteks funktsiooni filter : (a -> Bool) -> List a -> List a puhul kasutame implitsiitset parameetrit a eeldusel, et selles kontekstis pole a-l mingit definitsiooni.
Implitsiitse tüübiparameetri skoop on kogu defintsioon ehk, näiteks, filter-i tüübis (a -> Bool) -> List a -> List a kõik a-d on sama väärtusega ja seda a-d saab kasutada ka definitsioonis.
Näiteks, saame filter defineerida hoopis järgnevalt. Pane tähele, et let-is kasutatakse ka sama a-d.
| 1filter : (a -> Bool) -> List a -> List a 2filter p [] = [] 3filter p (x::xs) = 4 let rs : List a 5 rs = filter p xs in 6 if p x then x :: rs else rs |
Teine võimalus on eksplitsiitselt defineerida funktsioonile parameeter tüübiga Type ja anda väärtusele nimi. Seejärel saab defineetirud nime tüübis kasutada ning definitsioonis saab esimesele parameetrile anda uuesti nime. Näiteks saame listi pikkust arvutada järgnevalt defineeritud funktsiooniga length.
| 1length : (a: Type) -> List a -> Nat 2length t [] = 0 3length t (x::xs) = 1 + length t xs |
Sellist length definitsiooni kasutades peame esimeseks argumendiks andma list elementide tüübi ja teiseks argumendiks vastava listi. Vaata järgnevaid näiteid.
| Main> length Int [1,2,3] 3 Main> length Bool [True, False] 2 |
Selline eksplitsiitne tüübiparameetrite edastus on kohmakas, kuna tuleb infot korrata. Tegelikult, Idris suudab tihti vajaliku info ise tuletada — saame tüübiargumendi asendada alakriipsuga, näiteks length _ [True, False]. Seetõttu on Idrises võimalus märkida parameetrid implitsiitseks — nende väärtus tuleb tuletada teistest argumentidest. Implitsiitsed parameetrid tähistatakse loogeliste sulgudega. Vaata järgmist length' defintisiooni ja pane tähele, et definitsioonis ja väljakutsel me esimest argumenti ei maini.
| 1length' : {a: Type} -> List a -> Nat 2length' [] = 0 3length' (x::xs) = 1 + length' xs |
Implitiitseteks märgitud parameetreid saab definitsioonides ja mujal kasutada ka ekspltsiitselt — kasutades nimega parameetrite funktsioonikutse süntaksit. Näiteks, length' {a=Int} [1,2,3]. Nimedega paramteriseeritud funktsioontüübi puhul võime argumendid anda võrdustega, loogeliste sulgude vahel, komaga eraldatult. Argumentide järjekord pole oluline. Funktsiooni length' puhul anname a väärtuseks tüübi Int.
Siin on paslik mainida, et eksplitsiitse tüübiparameetriga funktsioon ei ole alati parameetrilise polümorfismi näide. Parameetrilisus tähendab selle mõiste puhul seda, et tulemus ei sõltu tüübist. Huvitava faktina, Idrises saab kirjutada funktsioone, mis sõltuvad tüübist. Näiteks, saame teha vigase listi pikkuse funktsiooni longth, mis ujukomaarvude listi puhul tagastab alati 0. Soovitame selliseid funktsioone mitte kirjutada.
| 1longth : (a: Type) -> List a -> Nat 2longth Double _ = 0 3longth t [] = 0 4longth t (x::xs) = 1 + longth t xs |
Parameetriline polümorfism on väga võimas tööriist. Polümorfismi, ehk mingi sümboli kasutamist erinevate tüüpide kontekstis, saab implementeerida lisaparameetrite (s.h. kasutades tüübiparameetreid) abil. Sellise lähenemise nõrgaks küljeks on koodi tekkivad parameetrid, mida ei saa alati implitsiitselt tuletada — kood muutub halvemini loetavaks. Loetavuse hoidmiseks on lisatud keelde Idris ka ad-hoc polümorfism.
Parameetriline polümorfism oli see, kui sama funktsioon töötab eri tüüpi andmetel olenemata tüübist. Ad-hoc polümorfism, seevastu, töötab erinevatel tüüpidel erinevate funktsioonidega. Näiteks, kui tahame sama funktsiooniga equal kontrollida täisarvude võrdust equal 4 5, sümbolite võrdsust equal 'x' 'x' ja sõnede võrdsust equal "abc" "123". Selline võrduse sümboli equal defineerimine ei ole parameetrilise polümorfismi kaudu otse võimalik. Kindlasti ei saa me teha equal funktsiooni tüübiga a -> a -> Bool, kuna näiteks Integer -> Integer funktsioonide võrdlemine ei ole praktiliselt võimalik — peaksime kontrollima funktsioonide tagastusväärtusi kõikide argumentide puhul.
Idrises saame defineerida liidese Equal a ning selle instantsid Equal Int, Equal Char jne.
| 1interface Equal a where 2 equal : a -> a -> Bool 3 4Equal Int where 5 equal a b = ?eq_Int -- Int'ide võrdsus 6Equal Char where 7 equal a b = ?eq_Char -- Char'ide võrdsus |
Kuigi liideses on kirjas equal : a -> a -> Bool, siis funktsiooni equal tüüp on tegelikult hoopis Equal a => a -> a -> Bool. Ehk, funktsiooni rakendamiseks kahele a-tüüpi argumendile peab leiduma instants Equal a. Kuna meil on defineritud Equal Int ja Equal Char siis saame saame kasutada equal-funktsiooni täisarvudel ja sümbolitel. Kuna meil pole instantsi funktsioonidele, siis tuleb tüübiviga, kui proovime täisarvude funktsioone võrrelda — vaata järgmist koodi.
| Main> equal 4 5 False Main> equal (\x => min x 1000) (\ x => x) Error: Can't find an implementation for Equal (Integer -> Integer). (Interactive):1:1--1:33 1 | equal (\x => min x 1000) (\ x => x) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
Idrise standardteegis on defineeritud tüübiklass Eq. Ehk samas liideses on defineeritud nii võrdumise kui mittevõrdumise kontroll. Minimaalne definitsioon peab sisaldama kas (==) või (/=) — puuduoleva funktsiooni definitsiooniks võetakse vaikedefinitsioon.
| 1interface Eq a where 2 (==), (/=) : a -> a -> Bool 3 x /= y = not (x == y) 4 x == y = not (x /= y) |
Kõikidel polümorfsetel funktsioonidel, mis kasutavad võrdsust, peab tüübi kontekstis olema kitsendus Eq. Näiteks polümorfne paaride listist otsimise funktsioon lookup võib olla defineeritud järgnevalt. Tüübi a elemente saab võrrelda tänu sellele, et kontekstis on kitsendus Eq a.
| 1lookup : Eq a => a -> List (a, b) -> Maybe b 2lookup _ [] = Nothing 3lookup x ((y,z)::ys) = if x==y then Just z else lookup x ys |
Konteksti ei ole mõtet lisada kitsendust konkreetsetele tüüpidele.
| 1eq_test : Eq Int => Int -> Int -- töötab ka: Int -> Int 2eq_test x = if x = 100 then 0 else x |
Liidestel võivad omakorda olla kontekstid — nii tekivad liideste hierarhiad. Näiteks Ord ty liidesel on kitsendus Eq ty. Ehk kõik täielikult järjestatud tüübid on ka võrduskontrolliga. Seetõttu võime kirjutada funktsioonile kitsenduse Ord a ja seejärel kasutada ka võrduskontrolli. Vaatame koodi Idrise standardteegist; minmaalseks implementatsiooniks piisab defineerida compare.
| 1interface Eq ty => Ord ty where 2 compare : ty -> ty -> Ordering 3 (<) : ty -> ty -> Bool 4 (>) : ty -> ty -> Bool 5 (<=) : ty -> ty -> Bool 6 (>=) : ty -> ty -> Bool 7 max : ty -> ty -> ty 8 min : ty -> ty -> ty 9 -- lisaks vaikedefinitsioonid |
Liidese instantsidele saab anda ka nime. Näiteks võime tahta defineerida naturaalarvudele tavalisest vastupidise täieliku järjestuse nimega revord.
| 1[revord] Ord Nat where 2 compare Z (S n) = GT 3 compare (S n) Z = LT 4 compare Z Z = EQ 5 compare (S x) (S y) = compare @{revord} x y |
Nüüd saame kasutada sorteerimsfunktsiooni sort : Ord a => List a -> List a (moodulist Data.List), kasutades nii tavalist järjestust ja ka vastupidist järjestust.
| Main> :import Data.List Imported module Data.List Main> sort [1,3,6,4,2] [1, 2, 3, 4, 6] Main> sort @{revord} [1,3,6,4,2] [6, 4, 3, 2, 1] |
Liidestel võib olla ka rohkem parameetreid kui üks, aga sellisel juhul ei pruugi kompilaatoril olla võimalik instantse automaatselt leida. Sellisel juhul võib olla abi sellest, kui märkida ära liidese määravad parameetrid. Süntaktiliselt tuleb peale liidese parameetreid kirjutada püstkriips ja anda komadega eraldatult määravad parameetrid. Näiteks, kui tahame defineerida täisarvude listide korrutamist täisarvuga, peame andma liidesele kolm parameetrit, mis vastavad korrutatavate tüüpidele ja tulemuse tüübile.
| 1interface Korda a b c | a, b where 2 mul: a -> b -> c 3 4Korda (List Integer) Integer (List Integer) where 5 mul xs y = map (*y) xs 6Korda Integer (List Integer) (List Integer) where 7 mul y xs = map (*y) xs |
Kui määravaid parameetreid Korda liideses mitte märkida, võib kompilaator jääda hätta liidese leidmisega. Näiteks avaldise mul [1,2,3] 5 tüüpimisel tuleb veateade "Error: Can't find an implementation for Korda (List Integer) Integer ?c"
Üldiselt on mõistlik vältida ülekattega instantse ja anda võimalikult üldised defintisioonid. Näiteks võiks Korda instantsid anda Integer asemel kõikidele tüüpidele, mis rahuldavad Num kitsendust. Liides Num defineerib nimelt liitmise (+) ja korrutamise (*).
| 1Num a => Korda (List a) a (List a) where 2 mul xs y = map (*y) xs 3 4Num a => Korda a (List a) (List a) where 5 mul y xs = map (*y) xs 6 7test_mul : List Double 8test_mul = 5.0 `mul` [1.0,2.0,1.2] |
Liideste ja instantside kohta saab infot standardteegi dokumentatsioonist ning Idrise REPL-ist. Näiteks, kui tahame teada, mis liides defineerib jagamise (/) siis piisab meil anda REPL-i käsk :doc (/). Saame teada, et jagamine on defineeritud kasutades Fractional tüübiklassi. Kirjutades :doc Fractional saame teada, et jagamine on Fractional-i meetod koos pöördväärtuse funktsiooni recip-ga ning et Num on Fractional-i kitsendus. Lisaks näeme, et vaikimisi on Fractional instants vaid ujukomatüübil Double.
| Main> :doc (/) Prelude.(/) : Fractional ty => ty -> ty -> ty Totality: total Visibility: public export Fixity Declaration: infixl operator, level 9 Main> :doc Fractional interface Prelude.Fractional : Type -> Type Parameters: ty Constraints: Num ty Constructor: MkFractional Methods: (/) : ty -> ty -> ty Fixity Declaration: infixl operator, level 9 recip : ty -> ty Implementation: Fractional Double |
Alampeatükis 6.5 vaatasime enumeratsioone. Nüüd näeme, et enumeratsioonid on lihtsalt erisüntaks liidesele Range. Näeme, et vaikimisi on defineeritud instantsid Range Nat, Range Nat ning (Integral a, Ord a, Neg a) => Range a.
| Main> :doc Range interface Prelude.Range : Type -> Type Parameters: a Constructor: MkRange Methods: rangeFromTo : a -> a -> List a -- [x..y] rangeFromThenTo : a -> a -> a -> List a -- [x,y..z] rangeFrom : a -> Stream a -- [x..] rangeFromThen : a -> a -> Stream a -- [x,y..] Implementations: Range Nat (Integral a, (Ord a, Neg a)) => Range a Range Char |
Alampeatükis 7.1 vaatasime listifunktsiooni map, mis on liidese Functor meetod. Functor on defineeritud näiteks tüübiperede Maybe ja List jaoks.
Funktsioonide foldl ja foldr vaatasime peatükkides 7.3 ja 7.2. Need on standardteegis liidese Foldable meetodid ning defineeritud näiteks tüübiperede Maybe ja List jaoks.
Lisaks on väga kasulik liides Show, milles on ainukeseks meetodiks on show, tüübiga Show a => a -> String. Funktsioon show saab kasutada enamike baastüübi väärtuste peal välja arvatud funktsioonid.
Väga kasulik on kahe argumendiga liides Cast a b, mille ainukeseks meetodiks on cast: Cast a b => a -> b. Funktsioon cast saab kasutada näiteks arvutüüpide vahel teisendamiseks. Samas tuleb siin olla ettevaatlik, kuna cast teisendused võivad olla kadudega. Näiteks the Nat (cast "5") on 5 aga the Nat (cast "-5") on 0.
Kasulikud liidesed on veel Applicative ja tema alamliides Monad. Nii Applicative ja Monad on tüübiperede liidesed, s.t. nende argumendid on tüübiga Type -> Type ehk argumentideks sobivad näiteks List ja Maybe. Mainitud liides Monad m modelleerib järjestikuseid arvutusi — kuid selleni jõuame varsti.
Monaadi Monad m intuitsioon üldiselt on, et m a tüüpi väärtused on "masinad, mille tulemus on a tüüpi väärtus." Olenevalt konkreetsest tüübiperest m, võivad monaadidel olla baas-"masinad".
Näiteks valime IO, ehk sisendit ja väljundit tegeva masina. Selle baas-"masinateks" on näiteks funktsioonid: sisendist lugemine, väljundisse kirjutamine ja juhusliku väärtuse arvutamine. Standardteegis on juhuarvude genereerimine defineeritud paketis contrib moodulis System.Random, ehk selle laadimiseks tuleb REPL-i käivitamiseks anda lipp -p contrib. Liidese Random instantsid on standardteegis vaid tüüpidele Int32 ja Double.
|
Intuitiivselt, funktsioon putStrLn võtab argumendiks sõne s ja tagastab masina, mis trükib konsooli sõne s ning tagastab väärtuse (). Funktsioon getLine on masin, mis ootab käsurealt sõne sisestamist ning tagagastab siis selle sõne. Funktsioon randomRIO võtab arvude paari ja tagastab masina, mis tagastab juhusliku arvu paaris olevate arvude vahemikus.
Aga mis kasu on meil masinast nagu putString "Tere, maailm!"? Kasu tuleneb sellest, et Idris oskab neid masinaid käivitada. Näiteks REPL-is saame anda käsu :exec, mille järel IO a tüüpi masin. Pane tähele, et masina käivitamisel selle tagastusväärtust välja ei trükita — juhuarv vahemikus nullist kümneni arvutatakse küll välja aga siis loobutakse sellest.
| Main> :exec randomRIO (0.0,10.0) Main> :exec putStrLn "Tere, maailm!" Tere, maailm! |
Monaadide liidesel on kaks peamist üldist meetodit: funktsioon pure ja operaator (>>=) ehk inglise keeles bind.
|
Funktsioon pure ütleb, et iga väärtuse x kohta leidub triviaalne masin pure x, mille ainuke tegevus on tagastada väärtus x.
Funktsioon (>>=) võtab argumendiks a-tüüpi väärtuse tagastava masina ning funktsiooni, mis iga a-tüüpi väärtuse kohta tagastab masina tüüpi m b. Funktsioonikutse s >>= f on masinate järjestikrakendus — kõigepealt käivitatakse masin s: m a ja saadakse tulemus x: a ja siis käivitatakse masin f x: m b ja saadakse tulemus y: b ning lõpus tagastatakse väärtus y.
Vaatame avaldist randomRIO (0.0,10.0) >>= (\\ x => putStrLn (show x)), mis koostab masina tüübiga IO (). Käivitades leitakse kõigepealt juhuslik ujukomaarv nulli ja kümne vahel ja siis trükitakse see välja.
| Main> :exec randomRIO (0.0,10.0) >>= (\ x => putStrLn (show x)) 0.03542536370122251 Main> :exec randomRIO (0.0,10.0) >>= (\ x => putStrLn (show x)) 5.870265901782135 |
Ühiktüüpi tagastava protseduuri komponeerimiseks saab kasutada operaatorit (>>), mis on defineeritud kui x >> y = x >>= (\ () => y). Intuitiivselt, masin x >> y käivitab masina x ning selle lõppedes käivitatakse masin y ning tagastatakse y-i tagastusväärtus. Vaata järgmist näidet.
| Main> :exec putStr "Tere" >> putStrLn ", maailm!" Tere, maailm! |
Kasutades tingimuslauset või mustrisobitust, saab implementeerida hargnemist; kasutades rekursiooni, saab implementeerida tsükleid. Vaata näiteks järgnevat üheargumendilist protseduuri trykiKuni, mis trükib erinevatele ridadeld numbrid argumendist kuni üheni.
| 1trykiKuni : Int -> IO () 2trykiKuni 0 = pure () 3trykiKuni n = trykiKuni (n-1) >> putStrLn (show n) |
| Main> :exec trykiKuni 3 1 2 3 |
Functor Tree ja Foldable Tree; kontrollige, et toList annab keskjärjestuse, kui on defineeritud
| 1data Tree a = Leaf | Branch (Tree a) a (Tree a) |
len : Foldable t => t a -> Int.
Rat, kus on üks konstruktor, mis võtab murru nimetaja ja lugeja. Implementeerige liidesed Eq, Num, Fractional ja Ord.
Monus, mis kirjeldab üldistatud lahutamise (mis ei pruugi rahuldada kõiki lahutamise omadusi). Andke instantsid vähemalt tüüpidele Nat ja Rat.
Set a = Tree a ()) ja implementeerige add, delete, intersect.