Polimorfie și cursuri în Haskell
Bună dragă cititor!
Astăzi vom vorbi despre polimorfismul funcției și despre clasele Haskell, cum să le folosim și pentru ce sunt. Cu toții am folosit metoda polimorfismului, de exemplu, în limbajul Java. Cum se poate aplica acest lucru la Haskell? Haskell nu este un limbaj orientat pe obiecte, dar are clase. Deși clasele din Haskell împărtășesc unele dintre proprietățile claselor în limbaje orientate pe obiecte, ele sunt mai abstracte și, prin urmare, mult mai puternice. Trasând o analogie cu limbajul Java, clasele din Haskell nu sunt altceva decât interfețe - în clasă sunt scrise doar declarațiile de funcții, iar implementările acestor funcții în sine vor fi făcute mai târziu. Aș dori să-mi exprim recunoștința față de utilizatorul Darkus pentru că a citit și corectat toate deficiențele și inexactitățile din articol, precum și pentru sfaturi practice și ajutor în scris.
Polimorfismul funcției
Există două tipuri de polimorfism în Haskell - parametrice și ad hoc (în engleză numit termenul „ad hoc”, care provine din limba latină).
Parametric
Dacă ați programat vreodată în Haskell, cu siguranță veți întâlni exemple de polimorfism parametric în funcțiile lungime, cap, teal, curry, uncurry, hartă, filtru, . . Ce unește toate aceste funcții? Să ne uităm la implementarea unora dintre ele:
Primele trei funcții au un parametru de intrare de tip a, în timp ce curry și uncurry au și b și c. În loc de un anumit tip de date (Int, Bool, Char, . ), se folosește tastarea. Exemplu in java:
Acest lucru folosește, de asemenea, A, un tip de date necunoscut care va fi determinat în momentul compilării. Polimorfismul este folosit atunci când nu se știe ce tip de date va fi parametrul, dar se cunosc operațiunile care se vor efectua asupra acestuia (sau cu el).
Toți identificatorii de variabile de tip din Haskell trebuie să înceapă cu o literă mică (de exemplu, a, abc, aA101 ), iar toate tipurile concrete (constructori) trebuie să înceapă cu o literă majusculă (de exemplu, String, Int, Node).
Parametrul a poate lua orice tip, fie el Int, String sau chiar funcții (de exemplu, lungime [f, g, h] , unde f, g, h sunt funcții care au aceleași tipuri). Este de remarcat faptul că tipul b poate lua orice tip, inclusiv tipul parametrului a .
Tipul unei funcții în interpretul GHCi (și în Hugs) poate fi întotdeauna găsit cu comanda :t, de exemplu:
Special (ad-hoc)
Sinonim cu polimorfismul ad-hoc este termenul „funcții supraîncărcate”. Acesta este un tip de polimorfism mai slab decât parametric. Să luăm ca exemplu operatorul de adăugare (funcția) (+). Expresii ca aceasta (+) 2 3 ->> 5 (+) 2,5 3,85 ->> 6.35 diferă de expresiile (+) Adevărat Fals (+) [1,2,3] [3,2,1] prin faptul că valorile numerice au fost folosite în prima caz, iar în al doilea tip Bool și [Int]. Operatorul de adăugare nu este definit pentru tipurile nenumerice. Acest lucru se datorează faptului că această funcție este de tipul nu (+) :: a -> a-> a și aceasta (+) :: Num a => a-> a-> A. Adică, aici se introduce o restricție asupra tipului de date de intrare (și de ieșire).
Constrângerea care este impusă tipului a : Num a spune că tipul a trebuie să fie un element al clasei Num. Astfel de clase de tip sunt foarte importante în Haskell, deoarece adaugă protecție suplimentară împotriva erorilor de programare și pot reduce, de asemenea, cantitatea de cod scrisă de câteva ori. Vom vedea acest lucru în exemplul următor.
Sunt date următoarele tipuri de arbori binari: Un arbore binar care poate stoca orice tip de date
Un arbore binar care poate stoca două elemente și fiecareramura se termină cu o „frunză” cu un element (nu Nil):
Un arbore binar care poate stoca date String și, de asemenea, se termină într-o frunză:
Și să presupunem că mai există două tipuri de liste: normale
Având toate aceste structuri de date, aș dori să scriu o dimensiune a funcției , care, indiferent de structura de date, ar scoate fie adâncimea (pentru arbori), fie lungimea (pentru liste), fie într-un cuvânt - dimensiune. O soluție naivă ar fi să scrieți o funcție separată pentru fiecare:
Acum, dacă apare orice altă structură de date, va trebui să creați o nouă funcție care se va potrividoarpentru această structură. Și ne-am dori să fie posibil să obținem dimensiuneaa oricărei structuri de datecu o singură funcție. Deoarece funcția (+) a avut o restricție cu clasa Num, trebuie să facem restricția cu clasa Size și pentru aceasta trebuie să o creăm mai întâi:
Rămâne doar să faceți instanțe (instanțe) din această clasă pentru valori specifice ale unui (=pentru anumite tipuri de date):
Gata! Acum, dacă scriem :t size în GHCi, vom vedea dimensiunea :: Size a => a-> Int . Am primit ce ne-am dorit:
Fiecare instanță a clasei Size a implementat o funcție de dimensiune care se aplică doar valorilor de un anumit tip (=structuri de date). În acest caz, această funcție, ca și alți operatori predefiniti (+), (*), (-), este supraîncărcată.
Dar o astfel de soluție are și dezavantajele ei. De exemplu, am dori să știm numărul de elemente dintr-o listă pereche, adică
Ar fi evident să faci următoarele:
Dar aici avem o problemă, deoarece avem deja o instanță pentru o listă obișnuită ( exemplul Size [a] unde ), nu mai putem folosi o altă definiție, deoarece, așa cum am menționat mai devreme, tipul a poate fi oricetip, inclusiv (b,c) , adică. [a] == [(b,c)] Instanțele suprapuse pot fi folosite pentru a rezolva această problemă. Această soluție are dezavantajele sale (importarea unuia dintre module poate schimba sensul programului, poate provoca erori confuze și așa mai departe). Acum puțin mai multe despre cursuri.
În exemplul anterior, am trecut clasa Size, dar iată o declarație incompletă a clasei în Haskell: (tv = tip variabilă):
Incomplet deoarece pot fi introduse și restricții la tv în declarația de clasă (de exemplu, tv trebuie să fie membru al clasei Ord). Pot exista orice număr de semnături, dar fiecare dintre ele trebuie să includă (ca parametru de intrare și/sau de ieșire) variabila tv. Clasele de tip sunt colecții de tipuri pentru care sunt definite funcții speciale. Iată câteva (unele dintre cele mai importante) clase din Haskell:
- Eq— clasă pentru testarea egalității (inegalității) a două tipuri de date (operații ==, /=)
- Ordeste o clasă pentru determinarea ordinii tipurilor, adică care element este mai mare, care este mai mic (operații >, >=, derivând ). Există și o dependență între clase. De exemplu, dacă știm să comparăm două elemente (clasa Ord), atunci trebuie să putem determina în prealabil dacă un element este egal cu celălalt (clasa Eq). La urma urmei, pentru a implementa operatorul ( >= ), trebuie să aveți un operator implementat (==). Prin urmare, putem spune că clasa Ord depinde (moștenește) de clasa Eq. Iată o diagramă mai detaliată a dependenței de clasă:
Să ne uităm la clasa de echivalență Eq mai detaliat. După cum sa menționat anterior, această clasă ar trebui să aibă două funcții (==) și (/=):
Codul arată că pentru orice instanță a clasei Eq, este suficient să implementați una dintre cele două funcții. De exemplu, pentru tipul Bool (douătipurile sunt egale numai atunci când ambele sunt adevărate sau false) acest lucru se face după cum urmează:
După cum puteți vedea, cazul Adevărat Fals și Fals Adevărat (precum și ultimul rând) nu este necesar să scrieți, deoarece inegalitatea este inversul egalității. Dacă înainte îl aveam astfel încât tipul să fie o cocretizare a altuitip(de exemplu, [Int] este o instanță de tip [a]), acum tipul poate fi o instanță a clasei(de exemplu, Bool este o instanță a clasei Eq). Prin aceeași analogie, puteți scrie funcțiile de egalitate ale acelor arbori binari pe care i-am folosit mai sus. De exemplu, pentru Tree2:
Pentru (Arborele3 a b) va trebui deja să impunem o condiție atât pe a cât și pe b , adică instanță (Eq a, Eq b) => Eq (Arborele 3 a b)
Orice în stânga => se numește context, totul din dreapta acestui simbol trebuie să fie fie un tip de bază (Int,Bool. ) fie constructori de tip (Arborele a, [. ]. ). Operatorul (==) este o funcție supraîncărcată (polimorfism ad-hoc).
Egalitatea (==) este o proprietate specifică tipului care necesită o implementare per tip (cum ar fi implementarea egalității de arbori binari). Aș dori să pot compara două funcții în acest fel:
Acest lucru ar necesita ca Haskell să scrie cod astfel:
Este posibil să scrieți o funcție care să returneze rezultatul egalității a două funcțiiorice(adevărat sau fals)? Din nefericire, din teza Church-Turing rezultă că egalitatea oricăror două funcții nu poate fi determinată. Nu există un algoritm care să decidă, pentru oricare două funcții date, întotdeauna și după un număr finit de pași dacă cele două funcții sunt egale sau nu. Un astfel de algoritm nu poate fi programat în niciun limbaj de programare.
În loc să implementați funcția pentru egalitate ca binararbori, puteți pune oricând acele clase care sunt moștenite automat de acest tip după cuvântul cheie care derivă. Adică am putea scrie destul de ușor:
Acest lucru ne permite să nu scriem noi înșine o instanță a clasei Eq (exemplare Eq a => Eq (Arborele a) unde . ). Dar pentru orice funcție, atunci trebuie să impuneți o condiție variabilei a ca această variabilă să fie un element al clasei Eq. Uneori, până la urmă, trebuie să scrieți singur aceste funcții, deoarece comparația „automată” nu funcționează întotdeauna așa cum ne-am dori. De exemplu, pentru un arbore binar
următoarea funcție va fi implementată (automat):
După cum putem vedea, primul argument al lui Node3 a fost omis, ceea ce nu ne-am dori în unele cazuri.
Concluzie
Numai utilizatorii înregistrați pot participa la sondaj. Intrati va rog.