10 - referenciák, case object

Scalában minden összetett típus (az $\mathrm{Int}$ , $\mathrm{Double}$, $\mathrm{Boolean}$, $\mathrm{Long}$ egyszerű típusok, ezekből a Java primitív típusai készülnek; de minden más típus) létrehozáskor a heap memóriában, dinamikusan jön létre. Vegyük például a $\mathrm{Pont}$ típust még egyszer:

case class Pont(x: Int, y: Int)

val p = Pont(2, 3)
val q = p

Ennek a kódnak a tényleges viselkedéséhez legközelebb álló C kód a következő:

typedef struct {
  int x;
  int y;
} Pont;

Pont *p = (Pont*)malloc(sizeof(Pont));
p->x = 2;
p->y = 3;
Pont *q = p;

Vagyis, amikor egy $\mathrm{Pont(2,3)}$ hívást intézünk, akkor dinamikusan, a heap memóriában lefoglalódik egy új memóriaterület, a két mezőnek megfelelő érték beáll a $2$-re ill. $3$-ra, majd ennek az újonnan létrehozott és tartalommal feltöltött memóriaterületnek végső soron a címe kerül a $p$ értékbe. 

Ezek után a $q=p$ értékadás hatására ez a cím másolódik át $q$-ba, így a két érték egy-egy "pointert" tárol, ami ugyanarra a memóriaterületre mutat.

(attól ne tartsunk, hogy nincs memória felszabadítás: a JVM mentalitása az, hogy nincs külön memória-felszabadító függvény, mint C-ben a $\mathrm{free}$, hanem a JVM mellett fut egy garbage collector, aki ha észreveszi, hogy egy memóriaterületre már nem mutat senki, felszabadítja automatikusan.)
Teljesen hasonlóan, a $\mathrm{Lista}$ case classunk is leginkább valami efféle lehetne C-ben:

typedef struct {
  int type; //0 üres, 1 nemüres
  union {
    struct UresLista *uresLista;
    struct NemuresLista *nemuresLista;
  };
} Lista;

typedef struct UresLista{
} UresLista;

typedef struct NemuresLista{
  int head;
  Lista *tail;
} NemuresLista;

// ures: egy UresLista
Lista *ures = (Lista*)malloc(sizeof(Lista));
ures->type = 0;
ures->uresLista = (UresLista*)malloc(sizeof(UresLista));

// egyelemu: NemuresLista( 3, ures )
Lista *egyelemu = (Lista*)malloc(sizeof(Lista));
egyelemu->type = 1;
egyelemu->nemuresLista = (NemuresLista*)malloc(sizeof(NemuresLista));
egyelemu->nemuresLista->head = 3;
egyelemu->nemuresLista->tail = ures;

Még egyszer: amit csak látunk és nem "primitív" típus, az mind valójában "referencia" (a különbség referencia és pointer között: a referencia nem $\mathrm{null}$, mindig egy valid objektumra mutat, nincs referencia-aritmetika, azaz nem tudjuk "eltolni" mint egy pointert, hogy egy tömbben "arrébb" indexeljünk, és szintaktikusan úgy kezeljük a referenciát, mintha egy tényleges objektum lenne - pl. ponttal és nem nyíllal hivatkozzuk a mezőit).
Ez azt is jelenti, hogy pl. egy Lista konstruálásakor valójában konstans idő alatt készül az új lista, mert nem másoljuk a farkát, csak elrakjuk a címét egy mezőbe.
Továbbá azt is jelenti, hogy az $==$ operátor először is a két oldalán lévő referenciák címét hasonlítja össze, és ha azok egyenlőek, akkor máris le tudja jelenteni, hogy $\mathrm{true}$; ha meg nem, akkor végignézi az adatmezők egyeztetését.
Mi a helyzet tehát akkor az üres listával:

case class UresLista() extends Lista

val list = UresLista()
val egyelemu = NemuresLista(5, UresLista())

Ahányszor csak létrehozunk egy $\mathrm{UresLista}$ értéket, mindig egy új rész foglalódik le neki a memóriában, ennek a címét megkapja az adott érték. Amikor meg $==$-t tesztelünk rá, és két külön helyen lévő "példányát" nézzük, hogy egyenlőek-e (azok lesznek, hiszen adattag nincs), akkor eltart egy darabig, mire rájön a JVM, hogy ezek nem ugyanazon a címen vannak, de ugyanolyan típusúak, és minden mezejük megegyezik.

Mindezt megspórolhatjuk, ha case class helyett $\mathrm{case~object}$ként deklaráljuk az üres listát:

case object UresLista extends Lista

val list = UresLista //nincs zárójel!
val egyelemu = NemuresLista(5, UresLista) //itt sincs

Egy case object lényegében egy olyan típus, aminek egyetlenegy elemű az értéktartománya (tkp ez igaz volt az $\mathrm{UresLista}$ra mint $\mathrm{case~class}$ra is, csak több helyen is létrehozhattuk a memóriában ezt az egy értéket), és ez az egy érték a program futása legelején létrejön egyetlen helyen a memóriában, és innentől kezdve minden értékadásnál ezt az egy referenciát kapja minden ilyen típusú érték. Ez többek közt azért jó, mert csak egyszer foglal helyet a memóriában és gyorsabb rá az $==$ ellenőrzés. Innen kezdve viszont nincs neki argumentumlistája (ha lenne, nem hozhatnánk létre egyetlen objectként), a zárójelek kitevése fordítási hibát is okoz.
Lényeg: ha egy típus valójában az $1$ típus, akkor azt $\mathrm{case~object}$ként hozzuk létre; ha extendelnie kell egy $\mathrm{trait}$et, azt is tudja probléma nélkül.
Az int listánk mostani implementációja tehát:

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

mintailleszteni pedig szintén tudunk case objectre, nem kell és nem is szabad kitennünk a zárójeleket, de egyébként ugyanúgy, mint korábban:

def find(list: Lista, value: Int): Boolean = list match {
  case UresLista => false
  case NemuresLista(`value`, _) => true
  case NemuresLista(_, tail) => find(tail, value)
}

Itt láthatunk egy eddig nem tárgyalt mintaillesztést: ha backtick-ek (`) közé rakunk egy azonosítót, akkor az nem egy új azonosító lesz, ami mindenre illeszkedik és behelyettesítődik jobb oldalra, hanem egy már létező azonosítóhoz tartozó érték kerül ide. Így ez a függvény azt adja vissza (farokrekurzív módon), hogy a paraméterként megadott listában előfordul-e a paraméterként megadott érték. Ha igen, akkor a második case illeszkedik akkor, amikor ahhoz a részlistához érünk, akinek a fejeleme pont a keresett elem (ekkor már mindegy, hogy mi a farok, ezért ott az underscore). Ha meg nem, akkor keresünk tovább a lista farkában (ekkor meg már nem számít, hogy mi is a fejelem; ha a harmadik case alternatívához érünk, akkor már tudjuk, hogy nem a keresett érték az). Vagyis, egy $\mathrm{case~NemuresLista}(`value`,\_)$ case egyenértékű egy $\mathrm{case~NemuresLista}(v,\_)~\mathrm{if}~v==value$ if guardos case-el.