Rekursiivinen tietotyyppi - Recursive data type

Tietokoneen ohjelmointikielet , eli rekursiivinen datatyypin (tunnetaan myös rekursiivisesti määritelty , induktiivisesti määritellyt tai induktiivinen tietotyyppi ) on tietotyyppi arvoja, jotka voivat sisältää muita arvoja samaa tyyppiä. Rekursiivisten tyyppien tietoja tarkastellaan yleensä suunnattuina kaavioina .

Tärkeä rekursiosovellus tietojenkäsittelytieteessä on dynaamisten tietorakenteiden, kuten luetteloiden ja puiden, määrittely. Rekursiiviset tietorakenteet voivat kasvaa dynaamisesti mielivaltaisesti suureksi vastauksena ajonaikaisiin vaatimuksiin; sen sijaan staattisen taulukon kokovaatimukset on asetettava kääntöhetkellä.

Joskus termiä "induktiivinen tietotyyppi" käytetään algebrallisiin tietotyyppeihin, jotka eivät välttämättä ole rekursiivisia.

Esimerkki

Yksi esimerkki on listan tyyppiä, Haskell :

data List a = Nil | Cons a (List a)

Tämä osoittaa, että luettelo merkinnöistä on joko tyhjä luettelo tai haittasolu, joka sisältää 'a' (luettelon "pää") ja toisen luettelon ("häntä").

Toinen esimerkki on samanlainen yksinkertaisesti linkitetty tyyppi Java:

class List<E> {
    E value;
    List<E> next;
}

Tämä osoittaa, että tyypin E tyhjä luettelo sisältää tyypin E datajäsenen ja viittauksen toiseen luettelo-objektiin loppuosan luettelossa (tai nollaviittauksen, joka osoittaa, että tämä on luettelon loppu).

Vastavuoroisesti rekursiiviset tietotyypit

Tietotyypit voidaan määrittää myös keskinäisellä rekursiolla . Tärkein perusesimerkki tästä on puu , joka voidaan määritellä vastavuoroisesti rekursiivisesti metsänä (puulista). Symbolisesti:

f: [t[1], ..., t[k]]
t: v f

Metsä f koostuu puulistasta, kun taas puu t koostuu arvon v parista ja metsästä f (sen lapset). Tämä määritelmä on tyylikäs ja sitä on helppo käsitellä abstraktisti (esimerkiksi todistettaessa puiden ominaisuuksia koskevia lauseita), koska se ilmaisee puun yksinkertaisella tavalla: yhden tyyppinen luettelo ja kahden tyyppinen pari.

Tämä molemminpuolisesti rekursiivinen määritelmä voidaan muuntaa yksittäin rekursiiviseksi määritelmäksi sisällyttämällä metsän määritelmä:

t: v [t[1], ..., t[k]]

Puu t koostuu arvoparista v ja puulistasta (sen lapsista). Tämä määritelmä on kompaktimpi, mutta hieman keskipitkämpi: puu koostuu yhden tyyppisestä parista ja luettelosta toinen, joiden tulosten todistaminen vaatii irrotuksen.

In Standard ML , puu ja metsä tietotyyppejä voidaan vastavuoroisesti rekursiivisesti määritellä seuraavasti, jolloin tyhjä puita:

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

Haskellissa puu- ja metsätietotyypit voidaan määritellä samalla tavalla:

data Tree a = Empty
            | Node (a, Forest a)

data Forest a = Nil
              | Cons (Tree a) (Forest a)

Teoria

In tyyppi teoria , rekursiivinen tyyppi on yleinen muoto μα.T jossa tyyppi muuttuja α saattaa näkyä tyyppi T ja tarkoittaa koko tyyppi itse.

Esimerkiksi luonnolliset luvut (katso Peano-aritmeettinen ) voidaan määrittää Haskell-tietotyypillä:

data Nat = Zero | Succ Nat

Tyypin Teoriassa sanoisimme: jossa molemmille summan tyyppiä edustaa Zero ja Succ tietojen rakentajat. Nolla ei ota argumentteja (jota edustaa näin yksikkötyyppi ) ja Succ ottaa toisen Natin (siten toisen elementin ). ${\ displaystyle nat = \ mu \ alpha .1+ \ alpha}$ ${\ displaystyle \ mu \ alpha .1+ \ alpha}$

Rekursiivisia tyyppejä on kahta: niin kutsutut isorekurssiiviset tyypit ja equirekurssiiviset tyypit. Molemmat muodot eroavat toisistaan siinä, miten rekursiivisen tyypin termit otetaan käyttöön ja poistetaan.

Isorekurssiiviset tyypit

Isorekursiivisissa tyypeissä rekursiivinen tyyppi ja sen laajentuminen (tai purkaminen ) (Jos merkinnät osoittavat, että kaikki Z: n esiintymät korvataan X: llä X: ssä) ovat erillisiä (ja disjoint) tyyppejä erityisillä termirakenteilla , joita yleensä kutsutaan roll and unroll , muodostavat isomorfismin niiden välille. Tarkemmin sanottuna: ja , ja nämä kaksi ovat käänteisiä funktioita . ${\ displaystyle \ mu \ alfa .T}$ ${\ displaystyle T [\ mu \ alpha .T / \ alpha]}$ ${\ displaystyle X [Y / Z]}$ ${\ displaystyle roll: T [\ mu \ alpha .T / \ alpha] \ to \ mu \ alfa .T}$ ${\ displaystyle unroll: \ mu \ alpha .T \ - T [\ mu \ alpha .T / \ alpha]}$

Equirecursive tyypit

Equirekursiivisten sääntöjen mukaan rekursiivinen tyyppi ja sen avautuminen ovat yhtä suuret - toisin sanoen näiden kahden tyyppilausekkeen ymmärretään tarkoittavan samaa tyyppiä. Itse asiassa suurin osa equirekurssiivisten tyyppien teorioista menee pidemmälle ja määrittelee olennaisesti, että kaikki kaksi tyyppilauseketta, joilla on sama "ääretön laajennus", ovat samanarvoisia. Näiden sääntöjen seurauksena equirekurssiiviset tyypit lisäävät huomattavasti monimutkaisuutta tyyppijärjestelmään kuin isorekurssiiviset tyypit. Algoritmiset ongelmat, kuten tyyppitarkistus ja tyyppijärjestelmän päätelmä, ovat vaikeampia myös equirekurssiivisille tyyppeille. Koska suoralla vertailulla ei ole järkeä equirekurssiivisella tyypillä, ne voidaan muuntaa kanoniseksi muodoksi O (n log n) -aikana, jota voidaan helposti verrata. ${\ displaystyle \ mu \ alfa .T}$ ${\ displaystyle T [\ mu \ alpha .T / \ alpha]}$

Equirecursive-tyypit sieppaavat itse- tai viittaavien tyyppimäärittelyjen muodon, joka nähdään menettely- ja olio- ohjelmointikielissä, ja syntyy myös objektien ja luokkien tyyppiteoreettisessa semantiikassa . Toiminnallisissa ohjelmointikielissä isorekurssiiviset tyypit (tietotyyppien varjossa) ovat paljon yleisempiä.

Tyyppisynonyymeinä

Rekursio ei ole sallittua tyyppisynonyymeinä Mirandassa , OCamlissa (ellei -rectypeslippua käytetä tai se on tietue tai muunnos) ja Haskellissa; joten esimerkiksi seuraavat Haskell-tyypit ovat laittomia:

type Bad = (Int, Bad)
type Evil = Bool -> Evil

Sen sijaan se on käärittävä algebrallisen tietotyypin sisään (vaikka sillä olisi vain yksi konstruktori):

data Good = Pair Int Good
data Fine = Fun (Bool -> Fine)

Tämä johtuu siitä, että tyyppisynonyymit , kuten typedefit C: ssä, korvataan niiden määritelmällä käännösaikana. (Tyyppisynonyymit eivät ole "oikeita" tyyppejä; ne ovat vain "aliaksia" ohjelmoijan mukavuuden vuoksi.) Mutta jos tätä yritetään rekursiivisella tyypillä, se silmukkaa loputtomasti, koska riippumatta siitä kuinka monta kertaa alias korvataan, se silti viittaa itseensä, esim. "Huono" kasvaa loputtomasti: Bad→ (Int, Bad)→ (Int, (Int, Bad))→ ....

Toinen tapa nähdä se, että taso välillisen (algebrallinen data tyyppi) on tarpeen, jotta isorecursive tyyppinen järjestelmä selvittää, milloin rulla ja avautua .

Katso myös

Huomautuksia

Tämä artikkeli perustuu aineistoon, joka on otettu ennen 1. marraskuuta 2008 Free On-line Dictionary of Computing -sovelluksesta ja sisällytetty GFDL : n version 1.3 tai uudemman "relicensing" -ehtoihin .

Languages

In other projects