12 - algebrai adattípusok: a Lista

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ő Pont, Haromszog és Kor típusokat ha fel akarjuk írni ezekkel a jelekkel:

Pont      = Int  x Int
Haromszog = Pont x Pont x Pont
Kor       = Pont x Double
Shape     = Haromszog + Kor

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ő).

Rekurzív összeg és szorzat típusok

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:

Lista        = UresLista + NemuresLista
UresLista    = 1
NemuresLista = Int x Lista

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 Pont), akkor ő ennek a két mező típusának a szorzata, ha három (mint a 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()

Ezt később azért megtanuljuk majd ennél eggyel kulturáltabban megcsinálni, de nézzük most meg a fenti Lista, UresLista, NemuresLista szerkezetet. Formailag rendben vannak: a Lista az egy összeg típus, a 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, sőt tudunk értékeket is 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 Lista? az UresLista() érték az UresLista típusnak egy értéke, a Lista meg egy összeg típus, tehát az értéktartományában benne van minden UresLista is (mind az egy), ezért az UresLista() az egy lista. Ha viszont az, akkor a NemuresLista(7,UresLista()) egy NemuresLista, hiszen az első argumentum egy Int, a második meg egy Lista.

De ha ő NemuresLista, akkor Lista is, mert az utóbbi egy összeg típus, amiben a NemuresLista is benne van. Hasonlóképp, eszerint a NemuresLista(2,NemuresLista(7,UresLista())) is nemüres lista, eszerint lista is, és addig pakolhatunk további Inteket a meglévők elé, ameddig csak akarunk (feltéve, hogy megelégszünk véges sok elemmel). Amit implementáltunk most: 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, head, és van neki egy további része, avagy farka, 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 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.

Algebrai adattípusok

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 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 ahogy a Lista esetében gondolkodtunk: 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''.

Egyenlőség ellenőrzése érték szerint ingyen van

Ha a fenti listákat az == operátorral összehasonlítjuk:

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

Az első összehasonlítás eredménye nem annyira meglepő: (1,2,7) == (4,2,7) persze hogy hamis kéne legyen, tényleg az is. A második összehasonlítás eredmnye talán az annak, aki már látott Javát: mindkét lista az (1,2,7) értéket veszi fel, de nem ugyanazok az objektumok a memóriában, teljesen különböző időben lettek létrehozva! Javában ilyenkor false lenne az összehasonlítás eredménye, mert az ottani alapértelmezett == operátor azt ellenőrzi, hogy ugyanoda mutat-e a két oldalon álló referencia, Scalában viszont, ha case classokkal dolgozunk, akkor megkapjuk velük az érték szerinti egyenlőség-tesztelést: pontosan akkor lesznek egyenlőek, ha ugyanazzal a típussal hoztuk létre őket (pl. mindkettő Kor vagy mindkettő NemuresLista), és az adattagjaik is rendre egyenlőek (rekurzívan, tartalom szerint összehasonlítva).

(Egyébként a Tuple is ezt csinálja: két tuple közt az egyenlőség akkor áll fenn, ha ugyanannyi mezőjük van, ezeknek a típusai rendre megegyeznek és minden koordinátán fennáll az egyenlőség.)

A pure funkcionális programozás során egyik alap módszere, hogy algebrai adattípusokon végzünk mintaillesztés alapján rekurzívan (lehetőleg persze tail rekurzívan, hiszen egy lista is lehet simán 20.000 elemű) műveleteket. Ebből a ,,mintaillesztés'' szót még nem néztük meg: ez lesz a következő poszt témája.

Kérdések, feladatok

---

Utolsó frissítés: 2021-02-07 23:06:47