Structură de date pur funcțională - Purely functional data structure

În informatică , o structură de date pur funcțională este o structură de date care poate fi implementată într-un limbaj pur funcțional . Principala diferență între o structură de date arbitrară și una pur funcțională este că aceasta din urmă este (puternic) imuabilă . Această restricție asigură că structura datelor are avantajele obiectelor imuabile: persistența (completă) , copierea rapidă a obiectelor și siguranța firului . Structuri eficiente de date pur funcționale pot necesita utilizarea unei evaluări și memoize leneșe .

Definiție

Structurile de date persistente au proprietatea de a păstra versiunile anterioare ale lor nemodificate. Pe de altă parte, structuri precum matrici admit o actualizare distructivă , adică o actualizare care nu poate fi inversată. Odată ce un program scrie o valoare într-un anumit index al matricei, valoarea sa anterioară nu mai poate fi recuperată.

În mod formal, o structură de date pur funcțională este o structură de date care poate fi implementată într-un limbaj pur funcțional , cum ar fi Haskell . În practică, înseamnă că structurile de date trebuie construite folosind doar structuri de date persistente, cum ar fi tupluri, tipuri de sumă , tipuri de produse și tipuri de bază, cum ar fi numere întregi, caractere, șiruri. O astfel de structură de date este neapărat persistentă. Cu toate acestea, nu toate structurile de date persistente sunt pur funcționale. De exemplu, o matrice persistentă este o structură de date care este persistentă și care este implementată folosind o matrice, deci nu este pur funcțională.

În cartea Structuri de date pur funcționale , Okasaki compară actualizările distructive cu cuțitele maestrului bucătar. Actualizările distructive nu pot fi anulate și, prin urmare, nu ar trebui folosite decât dacă este sigur că valoarea anterioară nu mai este necesară. Cu toate acestea, actualizările distructive pot permite, de asemenea, o eficiență care nu poate fi obținută folosind alte tehnici. De exemplu, o structură de date care utilizează o matrice și actualizări distructive poate fi înlocuită de o structură de date similară în care matricea este înlocuită de o hartă , o listă de acces aleatoriu sau un arbore echilibrat , care admite o implementare pur funcțională. Dar costul accesului poate crește de la timp constant la timp logaritmic .

Asigurarea faptului că o structură de date este pur funcțională

O structură de date nu este niciodată inerent funcțională. De exemplu, o stivă poate fi implementată ca o listă legată individual . Această implementare este pur funcțională atâta timp cât singurele operații din stivă returnează o stivă nouă fără a modifica vechea stivă. Cu toate acestea, dacă limbajul nu este pur funcțional, este posibil ca sistemul de rulare să nu poată garanta imuabilitatea. Acest lucru este ilustrat de Okasaki, unde arată că concatenarea a două liste legate între ele se poate face în continuare folosind o setare imperativă.

Pentru a se asigura că o structură de date este utilizată într-un mod pur funcțional într-un limbaj funcțional impur, module sau clase pot fi utilizate pentru a asigura manipularea numai prin funcții autorizate.

Utilizarea structurilor de date pur funcționale

Una dintre provocările centrale în adaptarea codului existent pentru a utiliza structuri de date pur funcționale constă în faptul că structurile de date mutabile oferă „ieșiri ascunse” pentru funcțiile care le utilizează. Rescrierea acestor funcții pentru a utiliza structuri de date pur funcționale necesită adăugarea acestor structuri de date ca rezultate explicite.

De exemplu, luați în considerare o funcție care acceptă o listă modificabilă, inserează un element în listă și returnează lungimea noii liste. Într-o setare pur funcțională, inserarea unui element nou în listă produce o listă nouă, dar nu o actualizează pe cea originală. Prin urmare, pentru a fi utilă, o versiune pur funcțională a acestei funcții va trebui să returneze atât lungimea listei, cât și noua listă. În cel mai general caz, un program convertit în acest mod trebuie să returneze „starea” sau „stocarea” programului ca rezultat suplimentar din fiecare apel de funcție. Se spune că un astfel de program este scris în stilul magazinului .

Exemple

Iată o listă de structuri de date abstracte cu implementări pur funcționale:

Design si implementare

În cartea sa Purely Functional Data Structures , informaticianul Chris Okasaki descrie tehnicile utilizate pentru proiectarea și implementarea structurilor de date pur funcționale, dintre care un mic subset este rezumat mai jos.

Lenea și memoizarea

Evaluarea leneșă este deosebit de interesantă într-un limbaj pur funcțional, deoarece ordinea evaluării nu schimbă niciodată rezultatul unei funcții. Prin urmare, evaluarea leneșă devine în mod natural o parte importantă a construcției structurilor de date pur funcționale. Permite efectuarea unui calcul numai atunci când rezultatul este de fapt necesar. Prin urmare, codul unei structuri de date pur funcționale poate, fără pierderea eficienței, să ia în considerare în mod similar date care vor fi utilizate în mod eficient și date care vor fi ignorate. Singurul calcul necesar este pentru primul tip de date; asta se va efectua efectiv.

Unul dintre instrumentele cheie în construirea unor structuri de date eficiente și pur funcționale este memoizarea. Când se face un calcul, acesta este salvat și nu trebuie efectuat a doua oară. Acest lucru este deosebit de important în implementările leneșe; evaluările suplimentare pot necesita același rezultat, dar este imposibil să știm care evaluare o va necesita mai întâi.

Analiza și programarea amortizate

Unele structuri de date, chiar și cele care nu sunt pur funcționale, cum ar fi matricele dinamice , admit operații care sunt eficiente de cele mai multe ori (de exemplu, timpul constant pentru matricele dinamice) și rareori ineficiente (de exemplu, timpul liniar pentru matricele dinamice). Amortizarea poate fi apoi utilizată pentru a demonstra că timpul mediu de funcționare al operațiunilor este eficient. Adică, cele câteva operații ineficiente sunt destul de rare și nu modifică evoluția asimptotică a complexității timpului atunci când este luată în considerare o secvență de operații.

În general, a avea operații ineficiente nu este acceptabil pentru structurile de date persistente, deoarece această operațiune poate fi numită de multe ori. Nu este acceptabil nici pentru sistemele în timp real, nici pentru cele imperative, în care utilizatorul poate solicita ca timpul necesar operației să fie previzibil. În plus, această imprevizibilitate complică utilizarea paralelismului .

Pentru a evita aceste probleme, unele structuri de date permit amânarea operațiunii ineficiente - aceasta se numește programare . Singura cerință este ca calculul operației ineficiente să se încheie înainte ca rezultatul său să fie efectiv necesar. O parte constantă a operației ineficiente este efectuată simultan cu următoarea chemare la o operațiune eficientă, astfel încât operațiunea ineficientă este deja realizată în totalitate atunci când este nevoie și fiecare operație individuală rămâne eficientă.

Exemplu: coadă

Cozile amortizate sunt compuse din două liste legate între ele: fața și spatele inversat. Elementele sunt adăugate la lista din spate și sunt eliminate din lista din față. Mai mult, ori de câte ori coada din față este goală, coada din spate este inversată și devine față, în timp ce coada din spate devine goală. Complexitatea de timp amortizată a fiecărei operațiuni este constantă. Fiecare celulă din listă este adăugată, inversată și eliminată cel mult o dată. Pentru a evita o operațiune ineficientă în care lista din spate este inversată, cozile în timp real adaugă restricția conform căreia lista din spate este atâta timp cât lista din față. Pentru a vă asigura că lista din spate devine mai lungă decât lista din față, lista din față este atașată la lista din spate și inversată. Deoarece această operațiune este ineficientă, nu se efectuează imediat. În schimb, este răspândit pe operațiunile ulterioare. Astfel, fiecare celulă este calculată înainte de a fi necesară, iar noua listă frontală este calculată în totalitate înainte de a fi necesară apelarea unei noi operații ineficiente.

Vezi si

Referințe

linkuri externe