Sildistatud ühend

Sildistatud ühend (inglise keeles tagged union) ehk variant, summatüüp või kaaskorrutis, on informaatikas andmetüüp, mis sisaldab mitut erinevat fikseeritud tüüpi. Korraga saab ühendil olla ainult ühte tüüpi väärtus ja silt ütleb, milline tüüp on hetkel kasutuses. Silti võib lugeda omamoodi metaandmeteks. Sildistatud ühendit saab käsitleda kui tüüpi, millel on mitu erinevat "juhtu", millest peab kõiki korrektselt käsitlema siis, kui tüüp tuleb kasutusse. Sildistatud ühendid on vajalikud, et defineerida rekursiivseid andmetüüpe – näiteks selleks, et komponent mõnele tüübile X sisaldaks väärtust, mis on omakorda tüübist X. Seda kasutatakse näiteks puude defineerimisel, kus on vajalik eristada harusid ja lehti.

Kirjeldus

Sildistatud ühendid on tähtsal kohal funktsionaalsetes programmeerimiskeeltes nagu ML ja Haskell, kus neid nimetatakse andmetüüpideks (terminist algebraline andmetüüp) ning kompilaator suudab tuvastada, et kõik ühendi juhud on käsitletud, mis aitab vältida igasuguseid vigu. Kompilatsiooniaegseid summatüüpe kasutatakse ka Rusti keeles, kus neid kutsutakse nimega enum. Sildistatud ühendeid on võimalik konstrueerida ka paljudes keeltes, milles puudub nende otsene tugi. Näiteks on neid võimalik luua keeltes nagu C, kus on olemas sildistamata ühendid võtmesõnaga union.

Sildistatud ühenditega keeltes käib sageli kaasas mõiste tüübikonstruktorist, millega on võimalik luua sildistatud ühendite tüüpe.

Sildistatud ühendi vaste matemaatikas on lõikumatu ühend ehk diskrimineeritud ühend, mis tavaliselt kirjutatakse $+$-märgiga. Kui on antud sellisest ühendist A + B mõni element, on võimalik tuvastada, kas element tuli hulgast A või B. Kui element asub mõlemas, eksisteerivad selle väärtustest kaks eraldiseisvat koopiat nii hulgas A kui ka hulgas B.

Tüübiteoorias kutsutakse sildistatud ühendit summatüübiks. Summatüüpidel on vastavussuhe korrutistüüpidega.

Näited

Kui soovime luua kahendpuu täisarvudest, peaksime ML-i keeles looma sellise tüübi:

datatype puu = Leht
              | Tipp of (int * puu * puu)

See on sildistatud ühend tüübinimega puu kahe juhuga: Leht (ingl. leaf), millega lõpeb üks puu teekondadest, ning Tipp (ingl. node), mis sisaldab täisarvu tüübiga int ning kahte väärtust omakorda tüübiga puu. Leht ja Tipp on väärtuste konstruktorid, mis lubavad meil luua näiteks sellise puu:

Tipp(5, Tipp(1, Leht, Leht), Tipp(3, Leht, Tipp(4, Leht, Leht)))

See kood vastab sellele puule:

Konstruktorite poolt moodustatav puu

Nüüd on võimalik kirjutada tüübikindel (ja rekursiivne) funktsioon, mis näiteks loendab, mitu tippu on puul:

fun loendaTippusid(Leht) = 0
  | loendaTippusid(Tipp(int, vasak, parem)) =
      1 + loendaTippusid(vasak) + loendaTippusid(parem)

C

C ei toeta otseselt sildistatud ühendite loomist, aga neid on võimalik luua sildistamata ühenditega union, juhul kui silt on iga kord rangelt kontrollitud:

enum ShapeKind { Square, Rectangle, Circle };

struct Shape {
    int centerx;
    int centery;
    enum ShapeKind kind; /* Uniooni silt */
    union {
        struct { int side; };           /* Ruut */
        struct { int width, height; }; /* Ristkülik */
        struct { int radius; };         /* Ring */
    };
};

int getSquareSide(struct Shape* s) {
    assert(s->kind == Square); /* programm seiskub, kui antud uniooni silt ei ole ruut */
    return s->side;
}

void setSquareSide(struct Shape* s, int side) {
    s->kind = Square;
    s->side = side;
}

/* ja nii edasi */

Programmi kiiruse mõttes on võimalik assert funktsioonid pärast eemaldada, kui vigade vältimine on kindel. C++ keeles on C++17-st saati saadaval tüübikindel sildistatud ühend std::variant.

Rust

Rusti keeles on sisseehitatud tugi sildistatud ühendite jaoks:

enum Tree {
    Leaf,
    Node(i64, Box<Tree>, Box<Tree>)
}

Rusti keeles on mustrisobituse jaoks saadaval võtmesõna match, mis nõuab kõigi võimalike juhtude käsitlemist:

fn add_values(tree: Tree) -> i64 {
    match tree {
        Tree::Node(v, a, b) => v + add_values(*a) + add_values(*b),
        Tree::Leaf => 0
    }
}

Rusti vigade käsitluse süsteem on rajatud selliste sildistatud ühendite peale. Näiteks Option<T> tüüp valikuliste väärtuste esindamiseks, mis saab olla kas None, kui väärtust ei ole, või Some(T), kui väärtus on olemas. See lubab keelel vältida nullviitade sattumist koodi.

Sarnane on Result<T, E>, mis lisab ka tüübi E veaobjektide esindamiseks vea korral. See lubab Rustil vältida traditsioonilist eranditöötlust, kus erandid tõusevad koodis kuni nad tabavad eranditöötlejat või programm seiskub täielikult.