08 - lista, algebrai adattípus

Most, hogy van összeg típusunk és szorzat típusunk, az alaptípusainkból elkezdhetünk ezekkel a műveletekkel komplexebb típusokat építeni. Például, az előző posztban szereplő $\mathrm{Pont}$, $\mathrm{Haromszog}$ és $\mathrm{Kor}$ típusokat ha fel akarjuk írni ezekkel a jelekkel:

$$\begin{align*}\mathrm{Pont} &= \mathrm{Int}\times\mathrm{Int}\\\mathrm{Kor} &= \mathrm{Pont}\times\mathrm{Double}\\\mathrm{Haromszog} &= \mathrm{Pont}\times\mathrm{Pont}\times\mathrm{Pont}\\\mathrm{Shape} &= \mathrm{Kor}+\mathrm{Haromszog}\end{align*}$$

Mondhatjuk úgy, hogy minden típust vagy összeg típusként definiálunk (és akkor ő más típusok összegeként áll elő), vagy szorzat típusként (és akkor ő más típusok szorzataként áll elő).

Ez így elég egyértelműnek látszik, és persze sok mindent így egymásra építve is össze tudunk rakni, de igazán érdekessé akkor válik, ha az egyenletek jobboldalán akár "egymástól való függőséget" is kialakíthatunk, pl. így:

$$\begin{align*}\mathrm{Lista} &= \mathrm{UresLista}+\mathrm{NemuresLista}\\ \mathrm{UresLista} &= 1\\\mathrm{NemuresLista} &= \mathrm{Int}\times\mathrm{Lista}\end{align*}$$

Az első kérdés, hogy mi az az $1$ ott az üres lista jobb oldalán? Ez egy szorzat típus, mégpedig az üres szorzaté. Ha egy szorzat típusnak két mezője van (mint a $\mathrm{Pont}$), akkor ő ennek a két mező típusának a szorzata, ha három (mint a $\mathrm{Haromszog}$), akkor ennek a háromnak - és ha nincs neki mezője egyáltalán, akkor ő nulla darab típusnak a szorzata. Ezt a szorzat típust jelöljük $1$-gyel, egy Scala implementációja lehet pl. eddigi tudásunk szerint a következő:

case class UresLista()

//működik is:
val ures = UresLista()

A többi formailagrendben van: a $\mathrm{Lista}$ az egy összeg típus, a $\mathrm{NemuresLista}$ pedig egy szorzat típus. OK, de ezek egymásra hivatkoznak! Mit jelent ez? Először is nézzük meg, hogy ezt ha Scalában lekódoljuk az eddigi ismereteink alapján, akkor vajon fordul-e:

trait Lista
case class UresLista() extends Lista
case class NemuresLista(head: Int, tail: Lista ) extends Lista

Lefordul, igen, sőt értékeket is tudunk definiálni:

val ures = UresLista()
val egyelemu = NemuresLista(7, ures)
val ketelemu = NemuresLista(2, egyelemu)
val haromelemu = NemuresLista(1, ketelemu)
val masikharmas = NemuresLista(4, ketelemu)
println(haromelemu) //NemuresLista(1,NemuresLista(2,NemuresLista(7,UresLista())))

Ezek szerint hogy mi is lehet egy $\mathrm{Lista}$? az $\mathrm{UresLista()}$ érték az $\mathrm{UresLista}$ típusnak egy értéke, a $\mathrm{Lista}$ meg egy összeg típus, tehát az értéktartományában benne van minden $\mathrm{UresLista}$ is (mind az egy),  ezért az $\mathrm{UresLista}()$ az egy lista. Ha viszont az, akkor a $\mathrm{NemuresLista}(7,\mathrm{UresLista}())$ egy $\mathrm{NemuresLista}$ , hiszen az első argumentum egy $\mathrm{Int}$, a második meg egy $\mathrm{Lista}$. De ha ő $\mathrm{NemuresLista}$, akkor $\mathrm{Lista}$ is, mert az utóbbi egy összeg típus, amiben a $\mathrm{NemuresLista}$ is benne van. Hasonlóképp, eszerint a $\mathrm{NemuresLista}(2,\mathrm{NemuresLista}(7,\mathrm{UresLista}()))$  is nemüres lista, eszerint lista is, és addig pakolhatunk további $\mathrm{Int}$eket a meglévők elé, ameddig csak akarunk (feltéve, hogy megelégszünk véges sok elemmel). Amit implementáltunk most: $\mathrm{Int}$ elemeknek egy egy irányba láncolt listáját: a lista vagy üres, vagy nem, ha nemüres, akkor van neki egy első eleme, avagy feje, $\mathrm{head}$, és van neki egy további része, avagy farka, $\mathrm{tail}$, ami szintén lista. Jelben egy listát zárójelek közé írt elem-felsorolással fogunk felírni, pl. a kód $\mathrm{masikharmas}$ listáját így: $(4,2,7)$, az üres listát pedig így: $()$. Az egyeleműt így: $(7)$. A lista fejeleme a bal oldalán szerepel.

Mindenesetre, algebrai adattípusnak nevezünk egy típust, ha definiálható a fentihez hasonló módon: ha fel tudjuk írni típusok egy rendszerét úgy, hogy minden típus vagy más típusok összege, vagy más típusok szorzata, a jobb oldalon a rendszerben deklarált típusokat és alaptípusokat használhatunk, melynek egyik eleme (most a $\mathrm{Lista}$) a kérdéses típus, akkor ez egy algebrai adattípus. Az értéktartományát pedig így határozhatjuk meg általános esetben is, mint most: kiindulva a legkisebb elemekből, iteratívan bővítve (ez oda-vissza hivatkozott típusoknál, ha van "alsó" építőkocka, végtelen iteráció lesz, de nem baj, el tudjuk képzelni, hogy ez mit jelent, csak azt, hogy "bármekkora lehet"). Egyébként ezt úgy is mondják, hogy az értéktartomány a "legkisebb fixpontja" ennek az "egyenletrendszernek".

Mivel pedig case class konstrukció, az egyenlőség vizsgálatot is megkapjuk hozzá:

println(haromelemu == masikharmas) //false
println(haromelemu == NemuresLista(1, NemuresLista(2, NemuresLista(7, UresLista())))) //true

tehát továbbra is, az $==$ tartalom szerint hasonlít össze, ha a típus is megegyezik és a mezők tartalma is (rekurzívan), akkor egyenlő a két objektum, egyébként pedig nem azok. Van hozzá továbbá kiíratás is, ugyanúgy, mint korábban a case classok esetében is volt.

A pure funkcionális programozás egyik alap módszere, hogy algebrai adattípusokon végzünk mintaillesztés alapján rekurzívan , lehetőleg persze farokrekurzívan, műveleteket. A következő posztban erre fogunk látni példákat, match kifejezésekkel.

folytköv