Listaműveletek

Utasítások

Valósítsd meg az alapvető listaműveleteket.

Funkcionális nyelvekben az olyan listaműveletek, mint a length, a map és a reduce, nagyon gyakoriak. Valósíts meg egy sor alapvető listaműveletet anélkül, hogy meglévő függvényeket használnál.

A megvalósítandó műveletek pontos száma és neve kurzustól függ, hogy elkerüljük a meglévő nevekkel való ütközést, de az általad megvalósítandó általános műveletek közé tartoznak:

• append (adott két lista, a második lista összes elemét fűzd az első lista végéhez);
• concatenate (adott egy sor lista, az összes lista minden elemét fűzd össze egyetlen lapos listává);
• filter (adott egy predikátum és egy lista, add vissza mindazon elemek listáját, amelyekre predicate(item) igaz);
• length (adott egy lista, add vissza a benne lévő elemek teljes számát);
• map (adott egy függvény és egy lista, add vissza azoknak az eredményeknek a listáját, amelyeket úgy kapsz, hogy minden elemre alkalmazod a function(item)-et);
• foldl (adott egy függvény, egy lista és egy kezdő akkumulátor, hajtsd (redukáld) az egyes elemeket balról az akkumulátorba);
• foldr (adott egy függvény, egy lista és egy kezdő akkumulátor, hajtsd (redukáld) az egyes elemeket jobbról az akkumulátorba);
• reverse (adott egy lista, add vissza egy listát az összes eredeti elemmel, de fordított sorrendben).

Figyelj rá, hogy a fold függvényeknek (foldl, foldr) átadott argumentumok sorrendje nem mindegy.

Megvalósítás

Ehhez a feladathoz az Odin paraméterpolimorfizmusát (közismertebb nevén a generikusokat) kell használnod. Ha még nem találkoztál ezzel a nyelvi elemmel, itt egy gyors áttekintés, hogy el tudj indulni.

A paraméterpolimorfizmus egy olyan programozási nyelvi funkció, amely lehetővé teszi a programozónak, hogy kevésbé legyen konkrét (vagyis általánosabb, innen a neve) a kódjában használt típusokkal kapcsolatban, miközben megőrzi a típusbiztonságot. Ez természetesen csak erősen típusos nyelveknél, mint amilyen az Odin, van így.

Kezdjük egy példával. Mondjuk, hogy egy tömb minden elemét meg szeretnéd növelni egy rögzített értékkel; elég egyszerű probléma.

incr_array_int :: proc(a: []int, by: int) -> []int {

    new_array := make([]int, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Mi van akkor, ha most ugyanerre a funkcióra a lebegőpontos számoknál is szükséged van?

incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {

    new_array := make([]f64, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

És aztán az előjel nélküli egészeknél, a 32 bites lebegőpontosoknál és így tovább?

Nemsokára rengeteg eljárásod lesz, amelyek pontosan ugyanazt csinálják, csak más típuson. Ha egyszer frissítened kell a logikát, akkor gondoskodnod kell róla, hogy minden változatnál megtedd, ami sok karbantartási munkát jelenthet. A másik bosszúság, hogy minden eljárásnak külön nevet kell adnod, mivel az Odin nem támogatja az implicit eljárás-túlterhelést. (Explicit túlterhelést persze használhatsz, de az egy másik feladat története.)

Az Odin, lévén gyakorlatias nyelv, megoldást kínál erre a paraméterpolimorfizmussal. Amíg a fordító a fordítás idején ki tudja találni egy paraméter típusát, addig adhatsz neki egy generikus nevet, például T-t. Írjuk át a fenti eljárásunkat:

incr_array :: proc(a: []$T, by: T) -> []T {

    new_array := make([]T, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Figyeld meg, hogy az összes típusjelölést (int vagy f64) lecseréltük T-re, és hogy a T első előfordulása előtt dollárjel ($T) áll. A $T típus mondja meg az Odin fordítójának, hogy a T név egy generikus név erre a típusra, amelyet a fordítás során a tényleges névvel helyettesít. És mivel a fordító most már ismeri a T generikus típust, ugyanazon típus további előfordulásait már csak a választott típusnévvel (T) kell megjelölni.

Most már írhatsz ilyen kódot:

a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)

Az első utasításban az Odin fordítója azonosítja az első paraméter típusát ([]int) a generikus paraméter típusával ([]$T), kikövetkezteti, hogy T = int, majd lefordít egy változatot, amelyben a T összes további előfordulását int helyettesíti (ez megegyezik a fenti specializált incr_array_int() változattal). Ha elhagynád a dollárjelet az első paraméter definíciójából, a fordító az aktuális csomagban és az importok listájában keresett volna egy T nevű típust, és valószínűleg ezzel a fordítási hibával tért volna vissza: Error: Undeclared name: T.

A második utasítás pontosan úgy működik, mint az első, csak itt a fordító a T-t f64-ként azonosítja.

A generikus típusoknak szokás egybetűs neveket adni (T-t és E-t használnak gyakran).

Mostanra elég sokat tudsz a paraméterpolimorfizmusról, más néven a generikus típusokról ahhoz, hogy belevágj a Listaműveletek feladatba.