Algebraisk datatype

I programmering af computere, især funktionel programmering og type teori, en algebraisk datatype er en slags sammensat type, dvs. en type dannes ved at kombinere andre typer. To almindelige klasser af algebraiske type er produkttyper, dvs. tupler og optegnelser, og typer sum, også kaldet mærkede fagforeninger eller variant typer.

Værdierne af en varetype typisk indeholde flere værdier, kaldet felter. Alle værdier af denne type har den samme kombination af felttyper. Sættet af alle mulige værdier af en varetype er set-teoretisk produkt af sættene af alle mulige værdier af dens felttyper.

Værdierne af en sum type er typisk inddelt i flere klasser, kaldet varianter. En værdi på en variant type er normalt lavet med en kvasi-funktionel enhed kaldet en constructor. Hver variant har sin egen konstruktør, der tager et bestemt antal argumenter med bestemte typer. Sættet af alle mulige værdier af en sum type er set-teoretiske sum, dvs. disjunkte forening, af sættene af alle mulige værdier af dens varianter. Opregnede typer er et specialtilfælde af typer sum, hvor konstruktører tager nogen argumenter, som præcis én værdi er defineret for hver type.

Værdier af algebraiske typer analyseres med mønster matching, som identificerer en værdi af dets constructor eller feltnavne og udtrækker data, den indeholder.

Algebraiske datatyper blev indført i Hope, en lille funktionelt programmeringssprog udviklet i 1970'erne på Edinburgh University.

Eksempler

En af de mest almindelige eksempler på en algebraisk datatype er enkelt bundet listen. En liste type er en sum type med to varianter, til en tom liste, og for kombinationen af ​​et nyt element x med en liste xs til at oprette en ny liste:

 er en forkortelse af konstruktionen. Mange sprog har særlige syntaks for lister. For eksempel, Haskell og ML bruger til, eller til, og firkantede parenteser til hele lister. Så ville normalt skrives som eller i Haskell, eller som eller i ML.

For et andet eksempel, vi i Haskell kan definere en ny algebraisk datatype,:

Her repræsenterer en tom træ, indeholder et stykke data, og organiserer data i grene.

I de fleste sprog, der understøtter algebraiske datatyper, er det muligt at definere parametriske typer. Der gives eksempler senere i denne artikel.

Noget der ligner en funktion, der er en data-konstruktør anvendt på argumenter af en passende form, hvilket giver en instans af datatypen, som typen konstruktør tilhører. For eksempel, de data konstruktøren er logisk en funktion, hvilket betyder, at give et heltal som et argument for producerer en værdi af typen. Som tager to argumenter af typen selv, datatype er rekursiv.

Operationer på algebraiske datatyper kan defineres ved hjælp af mønstertilpasning at hente argumenter. For eksempel overveje en funktion til at finde dybden af ​​en, gives her i Haskell:

Således er en givet kan konstrueres ved anvendelse af enhver af eller og vi skal matche for nogen af ​​dem henholdsvis at behandle alle tilfælde. I tilfælde af, mønstret ekstraherer undertræer og til videre forarbejdning.

Algebraiske datatyper er særligt velegnede til gennemførelse af abstrakte syntaks. For eksempel, følgende algebraiske datatype beskriver en enkelt sprog repræsenterer numeriske udtryk:

Et element af en sådan datatype ville have en form, såsom.

Skrive en evaluering funktion for dette sprog er en simpel øvelse; imidlertid mere komplekse transformationer også blevet muligt. For eksempel kan en optimering passere i en compiler skrives som en funktion tager et abstrakt udtryk som input og returnerer en optimeret form.

Forklaring

Det, der sker, er, at vi har en datatype, som kan være "en af ​​flere typer af ting." Hver "type ting" er forbundet med en identifikator kaldes en konstruktør, som kan opfattes som en slags tag for den slags af data. Hver konstruktør kan bære med sig en anden type data. En konstruktør kunne bære nogen data overhovedet, bære et stykke af data eller flere stykker af data.

Når vi ønsker at gøre noget med en værdi på dette træ algebraisk datatype, vi dekonstruere det ved hjælp af en proces kendt som mønstertilpasning. Det indebærer at matche dataene med en række mønstre. Eksemplet funktionen "dybde" over mønster-matcher sin argumentation med tre mønstre. Når funktionen kaldes, den finder det første mønster, der matcher sin argumentation, udfører eventuelle variable bindinger, der findes i en opskrift, og evaluerer udtrykket svarer til mønsteret.

Hvert mønster har en form, der minder om strukturen af ​​nogle mulige værdi af denne datatype. Den første mønster over blot matcher værdier af konstruktøren Tom. Det andet mønster ovenfor matcher værdier konstruktøren Leaf. Mønstre er rekursive, så da de data, der er forbundet med at konstruktøren er matchet med mønstret "n". I dette tilfælde et lille identifikator repræsenterer et mønster, der matcher nogen værdi, som derefter bindes til en variabel af samme navn i det foreliggende tilfælde, at en variabel "" er bundet til heltalsværdien lagret i datatype anvendes i udtrykket der skal evalueres.

Den rekursion i mønstre i dette eksempel er trivielt, men en mulig mere komplekst rekursive mønster ville være noget lignende. Rekursive mønstre flere lag dybe anvendes for eksempel i afbalancering rød-sort træer, som involverer sager, der kræver at kigge på farver flere lag dybt.

Eksemplet ovenfor er operationelt svarer til følgende pseudokode:

Sammenligningen af ​​dette med mønstertilpasning vil pege på nogle af fordelene ved algebraiske datatyper og mønstertilpasning. Først er type sikkerhed. Pseudokoden Ovenstående er afhængig af omhu for programmøren at ikke få adgang felt2 når konstruktøren er et Blad, for eksempel. Også den type Felt1 er forskellig for Leaf og Node, så den type system vil have svært at tildele en statisk type det på en sikker måde i en traditionel rekord datastruktur. Men i mønstertilpasning, er typen af ​​hver udvundet værdi kontrolleres på grundlag af de typer, der er angivet af den relevante konstruktør, og hvor mange værdier, du kan udtrække er kendt baseret på konstruktøren, så det ikke står disse problemer.

For det andet, i mønstertilpasning, compileren kontrollerer statisk, at alle sager behandles. Hvis en af ​​tilfældene af funktionen "dybde" ovenfor manglede, ville compileren udsende en advarsel, hvilket indikerer, at der ikke håndteres en sag. Denne opgave kan synes let for de enkle mønstre ovenfor, men med mange komplicerede rekursive mønstre, bliver svært for den gennemsnitlige menneskelige at håndtere opgaven. Tilsvarende kan der være mønstre, som aldrig passer, og compileren kan også kontrollere og udstede advarsler for disse, da de kan indikere en fejl i begrundelsen.

Må ikke forveksle disse mønstre med regelmæssige ekspressionsmønstre anvendes i snor mønstertilpasning. Formålet er magen til kontrollere, om et stykke data matcher visse begrænsninger, og hvis ja, udtrække relevante dele af det til forarbejdning, men mekanismen er meget forskellige. Denne form for mønstertilpasning på algebraiske datatyper kampe om de strukturelle egenskaber af et objekt i stedet for på tegnsekvensen af ​​strenge.

Teori

En generel algebraisk datatype er en muligvis rekursiv sum type produkttyper. Hver konstruktør tags en varetype at adskille den fra andre, eller hvis der kun er én constructor, datatype er en produkttype. Endvidere parameter typer af en konstruktør er de faktorer af produkttype. En parameterless constructor svarer til den tomme vare. Hvis en datatype er rekursiv, er hele sum af produkter pakket ind i en rekursiv type, og hver konstruktør ruller også datatype i den rekursive type.

For eksempel Haskell datatype:

er repræsenteret i form teori med konstruktører og.

Den Haskell List datatype kan også være repræsenteret i typen teori i en lidt anden form som følger :. Den oprindelige dannelse angivet en type funktion, hvis krop var en rekursiv type den reviderede udgave specificerer en rekursiv funktion typer. Bemærk, at vi nu også skal gælde funktionen til sin argumentation type i kroppen af ​​typen.

Med henblik på listen eksempel disse to formuleringer er ikke væsentligt anderledes men den anden form tillader en at udtrykke såkaldte indlejrede datatyper, dvs. dem, hvor den rekursive typen adskiller parametrisk fra originalen.

I mængdelære hvad der svarer til en sum type er en disjunkte forening - et sæt, hvis elementer er par, der består af et tag og et objekt af en type svarende til tag.

Programmeringssprog med algebraiske datatyper

Følgende programmeringssprog har algebraiske datatyper som et første klasses begreb:

  • Ren
  • Ceylon
  • F #
  • Haskell
  • Haxe
  • Håber
  • LOTOS
  • Kviksølv
  • Miranda
  • Nemerle
  • OCaml
  • Opa
  • Racket
  • Rust
  • Scala
  • Standard ML
  • Swift
  • Tom
  • Visual Prolog
  0   0
Forrige artikel Festivaler i Havana
Næste artikel Comic fantasi

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha