Az F# programozási nyelv

Magasabb rendű típusok és generic-ek

Az F# magasabb rendű típusai, mint a listák, tuple-ök vagy a függvénytípusok mind generikusak, ez azt jelenti, hogy különböző alaptípusokkal lehet őket példányosítani. Például: int list, string list, vagy az (int * int) list mind a generikus list típusból származnak. Hasonlóan, az int -> int vagy a string -> int típusok mind a generikus függvénytípusból származnak. Mind az F# beépített könyvtárai, mind a .NET tartalmaz még rengeteg generikus típust.

A generikus típusváltozók megértése

A generikus konstrukciók mindig típusváltozók segítségével vannak kifejezve, amik az F# szintaxisában a következőképpen néznek ki: 'a, 'b, 'key és így tovább. Például a generikus list típus így néz ki:

type 'a list = ...

A típusváltozót írhatjuk prefix módon, mint ahogy az előző példában láttuk, vagy írhatjuk akár postfix módon is:

type list<'a> = ...

Az értékek is lehetnek generikusak. Egy tipikus generikus érték a List.map függvény, amelynek szignatúrája a következőképpen néz ki:

val map : ('a -> 'b) -> 'a list -> 'b list

Minden alkalommal, amikor megnevezünk egy generikus típust vagy értéket, akkor az F# típusrendszere elvégzi a szükséges példányosításokat. Vegyük például a következő szignatúrájú egyszerű függvényt:

val dummy : string -> string * string

Ha ezt a dummy függvényt alkalmazzuk az előbb felírt szignatúrájú List.map generikus függvényre, akkor a következő példányosítások fognak megtörténni:

Így a map függvény visszatérési értékének a típusa (string * string) list lesz.

A generikus értékek és függvények (mint a List.map) teljesen szokványosak az F# nyelvben. Valójában annyira hétköznapiak, hogy a legtöbbször még a típusváltozókat sem szoktuk kiírni. Azonban van, amikor találkozhatunk olyan esettel, mikor ki vannak írva, például ha a Visual Studio mutatja meg nekünk a típust tooltip formájában. Ekkor ilyet is láthatunk:

val map<'a,'b> : ('a -> 'b) -> 'a list -> 'b list

Gyakran a típusváltozóknak implicit hatóköre van, ami az automatikus általánosítás (automatic generalization) szabályai szerint működik (lásd: Generikus függvények írása alfejezet). Ez azt jelenti, hogy új típusváltozók a legegyszerűbben úgy vezethetőek be, ha egyszerűen beleírjuk őket a típus annotációba.

let rec map (f : 'a -> 'b) (l : 'a list) =
    match l with
      | h :: t -> f h :: map f t
      | [] -> []

Azonban ha akarjuk, akkor írhatjuk őket explicite a definícióba is. Ekkor azonban minden explicit kiírt típusváltozót használnunk is kell az annotációban.

let rec map< 'a, 'b > (f : 'a -> 'b) (l : 'a list) =
    match l with
      | h :: t -> f h :: map f t
      | [] -> []

Generikus függvények írása

Az F# kulcsfontosságú képessége a kód automatikus általánosítása (automatic generalization). Az automatikus általánosítás és a típuskikövetkeztetés kombinációja teszi a legtöbb F# programot jóval egyszerűbbé, hatékonyabbá és általánosabbá. Illetve a kód újrafelhasználhatóságát is nagyban növeli. Az automatikus általánosítás nélküli nyelvek arra kényszerítik a programozókat, hogy kigondolják, és explicite írják le a függvények legáltalánosabb típusát, és ez sokszor annyira fárasztó, hogy a programozók nem veszik a fáradságot, hogy minél absztraktabb és általánosabban felhasználható függvényeket írjanak.

Például a típus paraméterek automatikusan kerülnek bele a függvény szignatúrájába, ha olyan egyszerű függvényt írunk, amelynek a paraméterei nem függenek semmitől.

let getFirst (a,b,c) = a

A kikövetkeztetett típus pedig:

val getFirst: 'a * 'b * 'c -> 'a

Itt a getFirst függvény típusa automatikusan lett generikusra kikövetkeztetve. A függvénynek 3 típusváltozója van, az eredmény pedig a tuple első elemének a típusa lesz. Az automatikus általánosítás akkor lép életbe, amikor a let vagy member definíciók nem kötik meg minden input és output paraméter típusát. Azt mondhatjuk, hogy az automatikus általánosítást a jelen lévő típusváltozókra alkalmazzuk, így végül olyan függvényt kapunk, ami több típussal is használható.

Az automatikus általánosítás különösen hasznos, ha a bemenő paraméter függvény típusú. Például a következő kap két függvényt és egy tuple -t és a két függvényt alkalmazza a tuple két elemére.

let mapPair f g (x,y) = (f x, g y)

És az általános kikövetkeztetett típus a következő:

val mapPair : ('a -> 'b) -> ('c -> 'd) -> ('a * 'c) -> ('b * 'd)

Fontos generikus függvények

Az F# és a .NET könyvtáraiban nagyon fontos generikus függvények is találhatók. Fontos ezek megértése (vagy legalább egy kép kialakítása arról, hogy hogyan is működnek), mivel az általunk írt F# kód néha automatikusan is generikussá válik, akár a programozó tudta nélkül is.

Generikus összehasonlítás

Az első ilyen primitív függvénycsoport a generikus összehasonlításhoz kapcsolódik, melyet gyakran szerkezeti összehasonlításnak (structural comparison) is neveznek. Minden alkalommal, mikor a < , > , < = , > = , = , < > , compare , min vagy max függvényeket használjuk az F# kódunkban, akkor gyakorlatilag generikus összehasonlítást használunk. Ezek az operátorok a Microsoft.FSharp.Core.Operators modulban találhatóak, amelyik minden F# programban automatikus megnyitódik. Fontos adatszerkezetek is használnak beépítetten generikus összehasonlítást, például ilyen a Microsoft.FSharp.Collections.Set vagy a Microsoft.FSharp.Collections.Map adatszerkezet. Az alapvető generikus összehasonlító operátorok szignatúrája a következő:

val compare : 'a -> 'a -> int
val ( = ) : 'a -> 'a -> bool
val ( < ) : 'a -> 'a -> bool
val ( < = ) : 'a -> 'a -> bool
val ( > ) : 'a -> 'a -> bool
val ( > = ) : 'a -> 'a -> bool
val ( min ) : 'a -> 'a -> 'a
val ( max ) : 'a -> 'a -> 'a

Ezek az operátorok mind a compare függvény segítségével vannak implementálva, amelyik 0-t ad vissza, ha az argumentumok egyenlőek, -1-et vagy 1-et, ha kisebb vagy nagyobb.

A legtöbb .NET-es típus implementálja a System.IComparable interfészt, így a generikus összehasonlítás ezeket az interfészeket is használja. Összehasonlítást használhatunk összetettebb típusokra is, például tuple-ök esetén is, ekkor balról jobbra haladó lexikografikus összehasonlítást használ az F#.

> ("abc","def") < ("abc","xyz");;
val it : bool = true

> compare (10,30) (10,20);;
val it : int = 1

És ugyanígy használható a generikus összehasonlítás listákra és tömbökre is.

Amikor összetett, új adatszerkezeten akarjuk használni a generikus összehasonlítást, akkor a következőket kell végiggondolnunk:

Generikus hashelés

A generikus összehasonlítás egyik fontos társa a generikus hashelés. Az elsődleges primitív függvény, amelynek hívására egy hash értéket kapunk az a hash függvény, amely szintén a Microsoft.FSharp.Operators modulban található.

A hash függvény szignatúrája:
val hash : 'a -> int

Amikor egyszerű szerkezetű típusokon használjuk a hash függvényt, akkor mindig egy egyedi int értéket kapunk vissza.

> hash 100;;
val it : int = 100

> hash "abc";;
val it : int = 536991770

> hash (100,"abc");;
val it : int = 1073983640

A generikus összehasonlításhoz hasonlóan a generikus hashelést is általában csak a beépített típusokra és algebrai adatszerkezetre (olyanokra, amelyek beépített alaptípusokból épülnek fel) használhatóak. A generikus hashelés új típusok esetén testreszabható a GetHashCode metódus felülírásával, vagy a Microsoft.FSharp.Core.IStructuralHash interfész megvalósításával.

Generikus pretty printer

Hasznos generikus függvény még az, amelyik képes bármilyen értéket formázottan kiírni. A legegyszerűbb mód ennek használatára a %A direktíva a printf függvényben, vagy pedig az any_to_string függvény:

val any_to_string : 'a -> string
És néhány példa:
> any_to_string (Some(100,[1.0;2.0;3.1415]));;
val it : string = "Some (100, [1.0; 2.0; 3.1415])"

> sprintf "result = %A" ([1], [true]);;
val it : string = "result = ([1], [true])"

Ezek a függvények a .NET és az F# reflexióját használják, hogy végigmenjenek az adott adatstruktúrán és formázottan jelenítsék meg az adatszerkezetet az értékekkel együtt. Az összetettebb típusok, mint például a listák, vagy a tuple-ök formázása az F# forrás szintaxisára hasonlít. A fel nem ismert értékeket a .NET-es ToString() metódus hívásával írják ki a pretty pinter függvények.

Generikus box, unbox

A box és unbox két nagyon hasznos generikus függvény arra, hogy az F# típusait egy "egységes" System.Object (F#-ban obj) típusra, illetve típusról konvertáljuk.

val box : 'a -> obj
val unbox : obj -> 'a

Nézzük pár példát, hogy hogyan is működnek ezek a függvények a valóságban:

> box 1;;
val it : obj = 1

> box "abc";;
val it : obj = "abc"

> let sobj = box "abc";;
val sobj : obj = "abc"

> (unbox< string > sobj);;
val it : string = "abc"

> (unbox sobj : string);;
val it : string = "abc"

Az unbox használata során általában meg kell adnunk egy cél típust. Ezt megtehetjük explicite úgy, hogy paraméterezzük az unbox függvényt (pl.: unbox< string > ), vagy megadhatjuk típusmegszorítás formájában is (pl.: unbox sobj : string). Ezek a formák ekvivalensek. Futtatás során az unbox-ok végrehajtása előtt még elvégez a rendszer egy ellenőrzést, hogy biztonságosan lehet-e a kiválasztott céltípusra konvertálni. Az obj típusú értékek tárolnak dinamikus típusinformációkat, és ha ezeknek ellentmond a kiválasztott céltípus, akkor a következő futási idejű kivétel váltódik ki:

> (unbox sobj : int);;
System.InvalidCastException: Specified cast is not valid.
at < StartupCode >.FSI_0014._main()
stopped due to error

Ezek a függvények azért is fontosak, mert sok .NET-es könyvtár nyújt további generikus függvényeket, melyeknek argumentumai obj típusúak lehetnek.

Generikus szerializálás

A .NET-es könyvtárak biztosítják egy implementációját a generikus szerializálásnak, ami egy egyszerű és gyors módja az adatok kimentésének, illetve hálózaton való átküldésének. A most következő rész felfogható egy példának is, amely megmutatja, hogy hogyan használhatóak a .NET-es könyvtárak az F#-ból a box és unbox függvények segítségével.

Először is definiálunk két függvényt a következő szignatúrával:
val writeValue : #System.IO.Stream -> 'a -> obj
val readValue : #System.IO.Stream -> 'a

A writeValue függvény kap egy bármilyen típusú értéket, és a megadott streamre írja ennek az értéknek a bináris reprezentációját. A readValue függvény megfordítja ezt a folyamatot, hasonló módon, mint ahogyan az unbox visszaalakítja a box hatását. Most nézzük meg a két függvény implementációját, amelyek a System.Runtime.Serialization.Formatters.Binary névtérben található .NET-es függvényeket is használnak.

open System.IO
open System.Runtime.Serialization.Formatters.Binary

let writeValue outputStream (x: 'a) =
    let formatter = new BinaryFormatter()
    formatter.Serialize(outputStream,box x)

let readValue inputStream =
    let formatter = new BinaryFormatter()
    let res = formatter.Deserialize(inputStream)
    unbox x

A box és unbox függvények használatára azért volt szükség az implementációban, mert a Serialize és a Deserialize függvények paraméterei és visszatérési értékei is obj típusúak. Most pedig nézzünk egy példát arra, hogy hogyan használható ez a két függvény arra, hogy egy Microsoft.FSharp.Collections.Map< string, string > típusú értéket a FileStream -be írjunk és onnan visszaolvassuk.

open System.IO
let addresses = Map.of_list [ "Jeff", "123 Main Street, Redmond, WA 98052";
                                            "Fred", "987 Pine Road, Phila., PA 19116";
                                            "Mary", "PO Box 112233, Palo Alto, CA 94301" ]

let fsOut = new FileStream("Data.dat", FileMode.Create)
writeValue fsOut addresses
fsOut.Close()
let fsIn = new FileStream("Data.dat", FileMode.Open)
let res : Map< string, string > = readValue fsIn
fsIn.Close()

A példában is látszik az, mint amiről már volt szó korábban, hogy a readValue használatakor meg kell adnunk explicite a kiolvasott érték típusát, mivel a readValue függvény unbox-ot használ. Ha a Map< string, string > helyére másféle típust írnánk, akkor futási idejű kivételt kapnánk, amikor vissza akarjuk olvasni az adatokat a FileStream-ről.

Generikussá tétel (Making things generic)

A következőkben megnézzük, hogy hogyan lehet a már meglévő kódjainkat generikussá (újrafelhasználhatóvá) tenni, és hogy hogyan jelöljük a generikus algoritmusok absztrakt paramétereit.

Generikus algoritmusok explicit argumentumok segítségével

Általános programozási technika F# programok esetén, hogy a függvények paramétereket várnak, melyek befolyásolják a működésüket, és így lesznek az algoritmusok még általánosabbak, és még jobban újrafelhasználhatóak. A következő egyszerű példa a legnagyobb közös osztó (highest-common-factor = HCF) meghatározásának generikus implementációja.

let rec hcf a b =
    if a=0 then b
    elif a < b then hcf a (b-a)
    else hcf (a-b) b

Azonban ez az algoritmus nem generikus, ugyanis csak integer értékeken működik. Valójában, habár a (-) operátor az F#-ban alapértelmezésben túlterhelt, mégis legalább az egyik operandus típusának ismertnek kell lennie már fordítási időben. Továbbá a konstans 0 egy integer, és nincsen túlterhelve.

Mindezek ellenére egészen könnyen generikussá tehető a fent említett függvény. Ahhoz hogy elérjük ezt, szükségünk van egy explicit nulla értékre, egy kivonó függvényre és egy rendezésre. Erre itt egy példa:

let hcfGeneric (zero,sub,lessThan) =
    let rec hcf a b =
        if a=zero then b
        elif lessThan a b then hcf a (sub b a)
        else hcf (sub a b) b
    hcf

A kikövetkeztetett, generikus szignatúra pedig a következő:

val hcfGeneric : 'a * ('a -> 'a -> 'a) * ('a -> 'a -> bool) -> ('a -> 'a -> 'a)

Ennek a generikus függvénynek az eredménye egy konkrét függvény, ami már használható.

let hcfInt = hcfGeneric (0, ( - ),( < ))
let hcfInt64 = hcfGeneric (0L,( - ),( < ))
let hcfBigInt = hcfGeneric (0I,( - ),( < ))

Itt tulajdonképpen példányosítjuk a különböző típusokra a generikus függvényünket és kihasználjuk a (-) operátor túlterheltségét is.

Generikus algoritmusok absztrakt objektumok segítségével

Az előző generikus implementáció 3, egymással összefüggő paramétert vár. Gyakori technika, hogy összecsomagoljuk az összetartozó paramétereket. Egyik lehetőség erre, hogy definiálunk egy rekord típust, ami ezt a három értéket/függvényt összefogja.

type Numeric< 'a > =
    { Zero: 'a;
       Subtract: ('a -> 'a -> 'a);
       LessThan: ('a -> 'a -> bool); }
let intOps = { Zero=0 ; Subtract=(-); LessThan=( < ) }
let bigintOps = { Zero=0I; Subtract=(-); LessThan=( < ) }
let int64Ops = { Zero=0L; Subtract=(-); LessThan=( < ) }
let hcfGeneric (ops : Numeric< 'a >) =
    let rec hcf a b =
        if a= ops.Zero then b
        elif ops.LessThan a b then hcf a (ops.Subtract b a)
        else hcf (ops.Subtract a b) b
    hcf
let hcfInt = hcfGeneric intOps
let hcfBigInt = hcfGeneric bigintOps

A kikövetkeztetett szignatúrák a következők:

val hcfGeneric : Numeric< 'a > -> ('a -> 'a -> 'a)
val hcfInt : (int -> int -> int)
val hcfBigInt : (bigint -> bigint -> bigint)