Programovací jazyk F# Speciální programovací jazyky Jiří Fišer MMXI
F# programovací jazyk
primárně funcionální jazyk vytvořený Microsoft Resarch pro platformu .NET původně port jazyka OCaml pro platformu .NET, v současnosti (verze 2) i některé vlastní rysy staticky typovaný striktní multiparadigmatický jazyk podporovaná paradigmata (pořadí podle důležitosti)
funkcionální paradigma (ve stylu jazyka ML)
objektové paradigma (OOP model platformy .NET)
procedurální paradigma
Rodokmen jazyka F# Clojure (2007)
F# (2003)
OCaml (1996)
Caml (1985)
Haskell (1990)
Miranda (1985)
Common Lisp (1984)
ML(1973)
Scheme (1975)
Lisp (1958)
Pro a proti:
pro
kvalitní vývojové prostředí (Visual Studio 2010), resp. rozšíření v Monodevelopu praktická použitelnost, včetně nabídek na pracovním trhu (ČR) dostatečná dokumentace a knihy (v angličině)
proti
komplikovanější syntaxe a sémantika (dáno především spojením původních funkcionálních prostředků a prostředků .NET) ne zcela jednotný typový systém (ML vers. NET)
Struktura jazyka .NET integrace OOP rozšíření (OCaml) funkcionální jádro Caml
tao presentace se zaměřuje především na funkcionální jádro jazyka vrstvy se částečně prolínají, např.
OOP třídy jsou potřeba pro poporu monád tj. čistě funkcionálního prostředku funkcionální nadstavba nad IEnumerable
Základní pravidla syntaxe
ve F# hraje odsazení syntaktickou roli tj. je nutné jej ; důsledně dodržovat tato pravidla:
odsazovat lze jen mezerami
jednotky na stejné synt. úrovni musí být zarovnány (zleva)
podřízené synt. jednotky jsou odsazeny
F# rozlišuje velká a malá písmena (navíc je zde dost silný úzus jejich používání!) poznámky: // řádkové (* dlouhé i víceřádkové *)
Funkce
funkce jsou v F# běžnými hodnotami tj. lze je anonymně vytvářet, předávat do jiných funkcí či z funkcí vracet (stejně jako například čísla) F# podporuje všechny základní funkcionální mechanismy
rekurze (s optimalizací koncové rekurze)
lexikální vazbu a uzávěry
currying
funkce vyšších řádů (funkcionály)
funkce a metody standardní knihovny .NET jsou integrovány jen částečně (nefunguje currying,nejsou kompatibilní s běžnými funkcionály)
Definice funkce
funkce jsou definovány pomocí konstrukce let: let mean x y = (x + y)/2.0
konstrukce váže v aktuálním kontextu funkci na symbol (s lexikální vazbou volných proměnných) překladač automaticky odvodí statický typ funkce, zde (float = System.Double): float -> float -> float zkratka za float -> (float -> float)
funkce je automaticky curryovaná, tj. je interpretována jako funkce s jedním parametrem vracející funkci s n-1 parametry
mean x y = (mean x) y
Volání funkce
ve volání funkce nemusí být parametry uzávorkovány a neoddělují se čárkou
mean 5.0 10.0
závorky se používají jen pro změnu priorit, přičemž samo volání má vyšší prioritu než operátory závorky kolem složitějších parametrů
mean (x + 2.0) (2.0 * y)
závorky kolem celého volání funkce
2.0 + (mean 3.0 x)
Lokální vazby a vnořené funkce
uvnitř funkcí lze provádět lokální vazby (= vazby v lokálním kontextu) vazby běžných hodnot let root a b c = let d = b*b – 4.0 * a * c -b + sqrt d
vazby funkcí (tzv. vnořené funkce, běžný ideom) let flip f = let g y x = f x y g
Operátory
binární operátory jsou v F# de facto binární funkce (liší se jen jejich infixová aplikace)
lze je volat jako funkce (prefixově) (+) 2 3 lze je definovat jako funkce (identif. musí být speciál. znaky) let (~~) x y = mean x y 5.0 ~~ 10.0
unární operátory se definují podobně, využívají se však pouze prefixově některé běžné operátory podporované přímo .NET knihovnami mají speciální chování (+, *, <, &&, apod.):
mohou být přetížené (různé chování pro různé typy)
pokud je lze předefinovat tak jen objektově (obdoba C#)
Rekurzivní funkce
rekurze se v F# běžně používá (je to funkcionální jazyk) rekurzovní funkce musí být explicitně definována pomocí konstrukce let rec koncová (tail) rekurze je optimalizována tj. OM(1) let fact x = let rec fact' x acc = if x = 1 then acc else fact' (x – 1) (x * acc) fact' x 1 pomocná (vnořená) funkce fact' provádí výpočet s dodatečným parametrem pro akumulaci hodnoty, vnější funkce je jen jednoduchá (nerekurzivní) obálka
Elementární datové typy
základní datové typy jsou stejné jako v C# pozor na rozdíly v názvech! int16 namísto short int64 namísto long float32 namísto float float namísto double, apod.
přidány jsou nové typy (typické pro funkc. jazyky), např. bigint = System.Numeric.BigInteger literál: 2500I
F# powerpack nabízí i BigRational
Implicitní přetypování
F# nikdy neprovádí implicitní přetypování !! dokonce ani mezi číselnými objekty, např.
int na float (double) float32 (float) na float (double) int16 (short) na int důsledek: u literálů je nutno důsledně uvádět datový typ (často pomocí suffixů) 2 2.0 2.0F 2u
int float float32 uint
2uy 2y 2I 2UL
byte byte bigint uint64
Explicitní typování
F# staticky odvozuje (infer) typy všech vázaných symbolů v programu (symbol odkazuje vždy jen jednu hodnotu během celé své existence v daném kontextu) v některých případech to však může být nejednoznačné či nemožné čísla (operace jsou přetíženy pro všechny číselné typy) let add x y = x + y //implicitně int -> int -> int let bigAdd (x:bigint) (y:bigint) = x + y let hypot (x:float) (y:float) = sqrt (x*x + y*y) //povinné
explicitní typy je třeba uvádět i u složitejších OOP objektů (především je-li využit objektový polymorfismus)
N-tice (tuple)
nejednoduššími strukturovanými hodnotami jsou ntice jsou neměnitelné (typické pro funkc. jazyk!) musí mít určen počet prvků (navíc nelze jednoduše transformovat n-tice s různými počty prvků) mohou být nehomogenní (= mouhou mít položky různých typů) zápis: (1, 2) (”Bill”, 5625875156m) ((true, 5), ”OK”) specifikace typu: int * int string * decimal (bool * int) * string
Použití n-tic
representace strukturované hodnoty (náhrada záznamu, struktury, položky databáze) (”Jiří Fišer”, 40, ”[email protected]”)
zabalení více návratových hodnot do jedné (podobně jako OOP vzor přepravka) let divMod x y = ( x / y, x % y) předání více parametrů jako jediné n-tice, což je bližší syntaxi a sémantice .NET let max (a,b) = if a > b then a else b
důsledně užíváno pro běžné .NET metody a funkce
nepodporuje currying → nevhodné pro funkc. konstrukce
Seznam (list)
standardní kolekcí jazyka F# je nemodifikovatelný seznam lispovského typu. Je izomorfní se seznamem ve Scheme a vnitřně representovaný binárním stromem.
literály: [1; 2; 3], [”Eliška”, ”Čertice”] [['a'], ['c', 'd', 'e']]
pro čísla: [1..100], [2..2..100]
seznamy musí být homogenní (položky stejného typu) syntaktická zkratka za strom vytvořený operací :: (přidání do seznamu zleva tj. cons) 1 :: 2 :: 3 :: [ ] tj. 1 :: ( 2 :: ( 3 :: [ ]))
namísto (destrukčních) operací car a cdr se využívá mechanismu tzv. unifikace vzorů
Označení typů kolekcí
pokud je potřeba označit typ hodnoty (resp. je vypsán v interaktivním shellu fsi), pak lze n-tice a seznamy vyjádřit následujícími typy n-tice: typ1 * typ2 * ... * typn, kde typi je typ i-té položky a n je počet položek příklady: int * int, (int * string) * float seznam: typ list kde typ je typ všech položek příklady: int list, (string * int) list
Unifikace vzorů (pattern matching)
prostředek pro větvení programu na základě struktury a typu dat (vysokoúrovňová náhrada switch) let rec length s = match s with | [] -> 0 //hodnota je prázdný seznam | x :: xs -> 1 + length xs //struktura x::xs
rozhodovat lze i na základě shody jednoduché hodnoty let simpleNumber n = match n with | 1 -> ”jedna” | 2 -> ”dve” | _ -> ”mnoho” //univerzální vzor
Polymorfismus
jazyk F# podporuje polymorfismus tj. lze vytvářet funkce které mohou zpracovávat hodnoty více než jednoho typu například funkce length zpracovává seznamy bez ohledu na typ jejich položek symbolické vyjádření typu funkce length je: 'a list -> int kde 'a je symbol libovolného typu (typová proměnná)
skutečný typ je odvozen a kontrolován při každém využití polymorfní funkce (v místě volání funkce) a to již při překladu tj. polymorfismus je statický je tudíž obdobou generických typů v C# (generika a funkcionální polymorfismus jsou v F# částečně sjednoceny)
Složitější vzory
vzory mohou být vnořené
předpokládejme následující strukturu seznamu [(”jf”, 1); (”pk”, 2); (”jf”, 3); (”jf”, 2); (”pk”, 1)]
kde řetězec je označení osoby a číslo známka let rec prumerProJF s = match s with | (”jf”, znamka) :: xs -> znamka + prumerProJF xs | _ :: xs -> prumerProJF xs | [] -> 0.0
Shrnutí vzorů vzor
příklad s čím se shoduje
vazba
literál
1
jen se shodnou hodnotou
ne
symbol
n
s čímkoliv
ano
univerzální _
s čímkoliv
ne
složený
se shodně strukturovanou hodnotou
možná u podvzorů
x::xs
Strážní podmínky
unifikace vzorů není schopna nahradit konstrukce s podmínkami (např. if), neboť testovat lze pouze strukturální shody a rovnost s literály unif. vzorů je proto nutno rozšířit o strážní podmínky, které umožňují testovaní libovolné relace nad navázanými hodnotami let rec contains item s = //typ 'a -> 'a list -> bool match s with | x::_ when x = item -> true | _::xs -> contains item xs | [] -> false
ve vzoru se proměnná může vyskytovat nejvýše jednou
| (x,x) nutno použít | (x,y) when x=y
Funkce s integrovanou unifikací
funkce, jejichž tělo tvoří pouze unifikace jednoho z parametrů s různými vzory jsou v F# dosti běžné a tudíž pro bě existuje syntaktická zkratka (pozor: unifikovaný parametr musí být poslední) funkcionál map: ('a -> 'b) -> 'a list -> b' list
let rec map f s = match s with | [] -> [] | x::xs -> (f x)::(map f xs)
let rec map f = function | [] -> [] | x::xs -> (f x)::(map f xs)
ve zkráceném zápise mizí poslední parametr (tj. ten, jehož hodnota je unifikována se vzory. Kam zmizel? Odpověď je spojena s anonymními funkcemi.
Lambda funkce
anonymní (lambda) funkce: fun seznam-parametrů -> výraz
příklady (v poznámce typ funkce): fun x -> x + 1I
//bigint -> bigint
fun a b -> (a, b) //'a -> 'b -> 'a * 'b fun∙(a,b) -> (b,a) //'a * 'b -> 'b * 'a fun x y -> if x > y then x else y //'a -> 'a -> 'a when 'a : comparison
někdy lze místo λ-fce použít částečné volání (currying) (max 5), List.map (max 5) //(int list -> int list)
Kde je chybějící parametr? nyní se můžeme vrátit k chybějícímu parametru: let rec map f = function | [] -> [] | xs::xs -> (f x)::(map f xs)
definuje formálně funkci s jedním parametrem (f), která je však definována pomocí anonymní funkce s dalším (v zápise skrytým) parametrem tj. v podobě explicitně curryované) zápis lze rozepsat pomocí běžné lambda funkce takto: let rec map f = fun x -> match x with | [] -> [] | x::xs -> (f x)::(map f xs)
Funkcionály
F# podporuje všechny běžné funkcionály a to buď přímo (operátory, komprehenze), nebo pomocí knihovních funkcí běžné skládání funkcí (f ○ g) f << g //('a -> 'b) -> ('c -> 'a) -> 'c -> 'b
obrácené skládání funkcí (přehlednější zápis) f >> g //('a -> 'b) -> ('b -> 'c) -> 'a -> 'c
reverzní volání (místo f x), běžný F# ideom x |> f //'a -> ('a -> 'b) -> 'b lze řetězit více volání (tzv. pipeline česky datovod) s |> filter (fun x -> x>0) |> fold (fun x y -> x * y) |> log10
Seznamové funkcionály
map List.map //('a -> 'b) -> 'a list -> 'b list
zip List.map2 //('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
fold left List.fold // ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
fold right List.foldBack // ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
filter List.filter //('a -> bool) -> 'a list -> 'a list
Seznamová komprehenze
funkcionály map a filter se používají relativně málo, neboť je zahrnuju speciální zápis tzv. seznamová komprehenze [for var in list do if condition then yield item-expression]
var = lokální proměnná (postupně jsou na ní vázány položky)
list = původní seznam (při mapování se nemění!)
condition = filtrovací podmínka (část s if je nepovinná)
item-expression = mapovací výraz (= map. funkce aplikovaná na proměnou var)
for x in seznam do if x > 0 yield 2*x sum (for x in seznam do yield List.length x)
Seznamová komprehenze (flat)
F# seznamové komprehenze podporují i tzv. řetězení podseznam tj. operaci flat yield – vloží svůj argument jako jediný prvek versus yield! – vloží postupně jednotlivé prvky svého argumentu (musí to být seznam)
[for x in [1 .. 5] do yield [1..x]] vrací [[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]]
[for x in [1 .. 5] do yield! [1..x]] vrací [1; 1; 2; 1; 2; 3; 1; 2; 3; 4; 1; 2; 3; 4; 5]
Permutace
různé typy seznamových komprehenzí lze ilustrovat například ve funkci vracející seznam všech permutací daného seznamu let (|~) s a = [for item in s do if a <> item then yield item] let rec permutation = function | [] -> [[]] | s -> [for item in s do yield! [for sp in permutation (s |~ item) do yield item::sp]]
typ funkce permutation: 'a list -> 'a list list when 'a : equality
Datový typ option
klíčovou roli v F# hraje typ složený option, který umožňuje rozšířit běžné typy o nepřítomnou nebo nedefinovanou hodnotu (označována jako None) běžné hodnoty rozšířeného typu lze získat voláním konstruktoru Some na hodnotu Some(5) //typ int option Some(”Frodo”) //typ string option
hodnotu None lze získat prostřednictvím stejnojmeneného bezparametrického konstruktoru None // typ 'a option (polymorfní)
základní přístup k objektům optional typů je možný pomocí unifikace vzorů
Unifikace vzorů s option obdoba operátoru ?? jazyka C# (null-coalesing operator) let (|?) x y = match x with | Some(v) -> v | None -> y
x je potenciálně nedefinovaná hodnota a y náhradní hodnota (použitá v případě nedefinovanosti x) Some(5) |? 0 //vrací 5 Some(0) |? 0 //vrací 0 seznam |> map (fun x -> x |? 0) |> sum
Algebraické typy
typ option je konkrétním příkladem tzv. algebraického typu algebraické typy umožňují snadno vytvářet nové typy pomocí skládání, při zachování přístupu k dílčím položkám pomocí unifikace vzorů libovolný algebraický typ lze popsat jako množinu
k1⨯T1 ∪ k2⨯T2 ∪ … ∪ kn⨯Tn
ki = konstruktor tj. jedinečný symbol (label) Ti = je kartézský součin libovolných typů (včetně definovaného typu tj. typy mohou být rekurzivníi) nebo prázdná množina
Výčtový typ
speciálním případem algebraických typů jsou tzv. výčtové typy u výčtových typů je ∀i Ti = ∅ tj. je to seznam symbolů (= bezparametrických konstruktorů) type color = | Gule | Azure | Vert | Sable | Argent | Or
výčtové typy v F# nejsou vázány na číselnou representaci jako v C# (a nejsou přímo převoditelné)
Pojmenované struktury
další specializovaným algebraickým typem jsou pojmenované struktury (v obecném zápise je n = 1) pojmenovaná struktura je n-tice hodnot libovolného typu opatřená symbolem-konstruktorem, jenž jednoznačně identifikuje hodnoty daného typu příklady: type complex = Complex of float * float type person = Person of string * int * int
jednotlivé prvky struktury jsou určeny jen pozičně a jejich sémantika je zřejmá jen z použití! místo pojmenovaných struktur lze využít záznamy (record) = n-tice s pojmenovanými členy
Konstruktory a jejich funkce
konstruktory mají dvojí funkci:
1. vytvářejí hodnoty (tj. skládají hodnoty) 2. slouží jako vzor pro unifikaci (tj. hodnoty rozkládají) funkce je dána syntaktickou pozicí konstruktoru: let conjugate = function | Complex(re,im) -> Complex (re, - im) let makeSmarter = function | Person(name,age,iq) -> Person(name, age, iq+10) let name = function | Person(name, _, _) -> name
Obecné algebraické typy
obecné algebraické typy lze chápat jako sjednocení symbolických konstant a jedné či více množin struktur, přičemž hodnoty těchto jsou odlišeny návěštími type schoolHolidays = | Break of yearDate * yearDate | StateHoliday of yearDate | Easter let duration = function | Break(from,to) -> interval to from | StateHoliday _ | Easter -> 1 //yearDate must be implemented (as algebraic type?)
Rekurentní typy
algebraické typy mohou být rekurentní (tj. hodnota je soustavou navzájem vnořených hodnot stejného typu) následující typ representuje výrazy predikátové logiky (výrazy nikoliv hodnoty!) type logterm = | True | False | Not of logterm | And of logterm * logterm | Or of logterm * logterm | Impl of logterm * logterm //implikace | Equiv of logterm * logterm //ekvivalence příklad hodnoty typu: Equiv(And(Not a, Not b), Not (Or(a,b)))
Zpracování rekurzivních typů
není překvapivé, že rekurentní typy se nejlépe zpracovávají pomoci rekurze let rec eval = function | True -> true | False -> false | Not(term) -> not (eval(term)) | And(term1, term2) -> eval(term1) && eval(term2) | Or(term1, term2) -> eval(term1) || eval(term2) | Impl(term1, term2) -> eval(term1) <= eval(term2) | Equiv(term1, term2) -> eval(term1) = eval(term2)
nad jednotlivými rekurentními typy lze definovat obdoby běžných seznamových funkcionálů (map, fold)
Polymorfní algebraické typy
algebraické typy mohou být polymorfní tj. moho obsahovat položky předem neurčeného typu konkrétní typ položek se odvodí podle konkrétního použití (již při překladu) příkladem je např. algebraický typ pro binární stromy (který je navíc rekurentní) type 'a btree = | Node of 'a * 'a btree * 'a btree | Stub
tj. strom je tvořen vnitřními uzly (mají vždy dva poduzly typu a' btree a uloženou hodnotou typu 'a) nebo pahýly resp.listy (koncovými uzly bez potomků)
Binární strom
dva příklady funkcí nad binárnímy stromy let rec add item = function | Stub -> Node(item, Stub, Stub) | Node(num, left, right) when item <= num -> Node(num, add item left, right) | Node(num, left, right) -> Node(num, left, add item right) let fromList = List.fold (flip add) Stub let toListDF tree = let rec toListDF' tree acc = match tree with | Node(n, l, r) -> acc |> toListDF' r |> cons n |> toListDF' | _ -> acc toListDF' tree []
Aktivní vzory
přímé použití vzorů je možné jen u vestavěných a algebraických typů nikoliv u běžných .NET tříd F# proto podporuje možnost vytvoření (sekundárních) vzorů pro libovolný datový typ nejjednodušším případem je mapování podmnožin hodnot daného typu na symbolické konstanty let (|Workday|Weekend|) (date : DateTime) = if date.DayOfWeek >= DayOfWeek.Monday && date.DayOfWeek <= DayOfWeek.Friday then Workday else Weekend
aktivní vzory nelze samozřejměpoužít jako konstruktory
Aktivní vzory II
o něco složitější jsou vzory mapující původní typ na obecné algebraické typy (tj. na vzory s parametrem) let (|YearDuration|) year = //zjednodušeno!! YearDuration( if year % 4 = 0 then 366 else 365) využití let testYear = function | YearDuration(365) -> "normal year" | YearDuration (366) -> "leap year" | YearDuration(n) -> "abnormal year " + n.ToString()
dále jsou podporovány i aktivní vzory s dodatečnými parametry a otevřené vzory (mohou existovat i nemapované hodnoty) za využití typu option
Kontrola měrných jednotek
inovativním rysem F# je využití vyspělého typového systému pro kontrolu konzistence měrných jednotek při překladu (=staticky) měrné jednotky určují sémantiku hodnot a musí být využívány konzistentně (příkladem jsou fyzikální jednotky) (1) 1m ≠ 1kg //číselná shoda, sémantický rozdíl (2) 6N = 2kg * 3m^2/s^2 //komplexní vztahy mezi jednotkami
měrné jednotky lze representovat pomocí klasického typového systému, komplexní vztahy (viz 2) by však vyžadovaly vytvoření nového typu pro každou složenou jednotku a explicitní předefinování operátorů (+,*,/)
Měrné jednotky a typový systém
F# definuje měrné jednotky jako nadstavbu klasického typového systému tj. přkladač během překladu vytváří dodatečná metadata pro číselné typy (v rámci stat.odvození typu)
[+] kompatibilita s s typovým systémem .NET v generovaném kódu jsou použity jen klasické číselné typy – float a int, lze jej tedy volat např. z C# [+-] není nutno rozšiřovat sémantiku typů speciální podpora zajišťují automatické odvození složených typů je k dispozici pouze pro měrné jednotky nikoliv obecné typy [-] za běhu nejsou údaje o měrných jednotkách k dispozici (ani např.pro účely tisku jednotky ve výstupu)
Měrné jednotky v praxi
definice nového typu (de facto podtypu typu float nebo int) [<Measure>] type m [<Measure>] type s [<Measure>] type kg [<Measure>] type J = (kg * m^2)/(s^2) [<Measure>] type cal //není definován vztah k J označení číselných konstant 1.0 (nikoliv 1), 2.3<s>, 5<m/s>
povinné typování parametrů funkcí (typ návratové hodnoty může odvodit překladač) let cineticEnergy mass : float velocity : float<m/s> = 0.5 * mass * velocity * velocity
Měrné jednotky II
pro převod mezi jednotkami vyjadřujícími stejnou veličinu je nutno definovat pomocné funkce: všimněte si typování převodních koeficientů let toCal energy : float<J> = 0.2388459/1.0<J> * energy let toKelvin t : float = t * 1.0 / 1.0 + 272.15
někdy je nutné z důvodů kompatibility získat bezrozměrné číslo (pozor: většinou je to příznak rozměrové chyby!) let kgToFloat mass : float = mass / 1.0
Měrné jednotky III
definice SI fyzikálních jednotek obsahuje sestava (assembly) F# PowerPack (FSharp.PowerPack.dll) jmenný prostor
Microsoft.FSharp.Math.SI
Další typy kolekcí
F# podporuje i další kolekce resp. kolekcím podobné objekty
pole (array) – modifikovatelná kolekce převzatá z .NET (efektivní, ale mekomapatibilní s fukcionálním stylem) množina (set) – efektivní implementace nemodifikovatelné množiny (unikátnost položek, není uspořádání) sekvence (seq) – potenciálně neohraničená posloupnost položek, lenivé vyhodnocení = implementované pomocí .NET rozhraní IEnumerable
klíčová je podpora sekvencí, které tvoří de facto lenivý protějšek běžných seznamů (lenivý subsystém ve striktním jazyce)
Sekvence
zpracování sekvencí je v zásadě shodné se zpracováním seznamů
lze používat stejné funkcionály (jen v jm. prostoru Seq) lze používat operaci head, tail (v podobě skip 1) (nikoliv však vzor ::)
existují však i oblasti, kde se sekvence od seznamů zásadně liší
vytváření (generování) sekvencí sekvence nelze definovat přidáváním prvků zprava nelze aplikovat operace vyžadující přítomnost všech prvků (např. reverse, length), konečné sekvence však lze převést na seznamy
Vytváření sekvencí
konečné sekvence
interval seq {0I ... 100000I}
sekvenční komprehenze seq {for x in [1..10] yield 6*x-1}
nekonečné sekvence
rekurze let allEvens = let rec loop x = seq { yield x; yield! loop (x + 2) } loop 0
generující funkcionály
Funkcionály generující sekvenci initInfinite : (int -> 'T) -> seq<'T> funkce mapuje indexy na položky sekvence Seq.initInfinite (fun n -> 2*n) unfold : ('S -> ('T * 'S) option) -> 'S -> seq<'T> funkce vytváří další položky typu T na základě přeneseného stavu (typu S). Vrací option, aby mohla representovat konec sekvence (None). let fibs = (0I, 1I) |> Seq.unfold (fun (a, b) -> Some(a, (b, a + b) ) )
Funkcionály nad sekvencemi
generování sekvence prvočísel pomocí Eratosthenova síta (instruktivní, ale pomalé) pomocné funkce: let n = Seq.initInfinite (fun x -> x + 2) // N-{0,1} let head = Seq.head let tail = Seq.skip 1 let nondivisor d x = x % d <> 0 a můžeme definovat funkci let rec esito s = seq {yield head s; yield! esito (filter (nondivisor (head s)) (tail s))}
Převod na seznamy a vice versa
n prvních prvků ze sekvence lze získat pomocí funkce Seq.take (vrací konečnou sekvenci) konečné sekvence lze převést na seznamy pomocí seq.toList p = esito n //sekvence prvočísel Seq.toList(Seq.take 10 p) => [2; 3; 5; 7; 11; 13; 17; 19; 23; 29]
opačný směr: Seq.ofList(list) podobné funkce existují i pro převod mezi ostatními sekvencemi (např. List.ofSeq), ne vždy však v párech např. existuje jen Set.toList, Set.ofSeq, apod.)
Proměnná data
F# není čistě funkcionální jazyk a umožňuje používat modifikovatelné hodnoty (např. OOP objekty) či dokonce vytvářet celé programy v imperativním stylu F# se však snaží oba světa oddělit a v maximální míře zamezit negativním důsledkům použití imperativního kódu ve funkcionálním prostředí definice a inicializace proměnné let mutable i = 5 změna hodnoty (přiřazení): i <- 10
modifikovatelné hodnoty lze měnit jen v aktuálním kontextu (nikoliv např. v uzávěrech)
Měnitelné záznamy
nejdůležitější měnitelnou kolekcí je záznam (= pojmenovatelná n-tice) v rámci záznamu lze specifikovat jaké položky jsou měnitelné (implicitně jsou samozřejmě konstantní) type product = { ID : int; mutable price : decimal; } let processProducts (items) = items |> List.iteri (fun i item -> item.price <- (float i))
Reference
měnitelné záznamy lze využít pro přenos měnitelné hodnoty vně funkce a její sdílení F# záznamy využívá v předdefinovaném typu ref (funguje jako měnitelná reference) type 'a ref = { mutable contents : 'a } let ref v = { contents = v } let (!) r = r.contents let (:=) r v = r.contents <- v
využití let x = ref 100 x := 200 !x
Měnitelné kolekce
dalším typem měnitelných dat jsou pole a kolekce .NET
speciální podpora existuje jen pro pole let names = [| "Jitka"; "Jana"; "Jiřina"|] names.[2] <- "Judita" names.[1..2] //řezy (slices) tj. podpole
podporovány jsou i vícerozměrná pole (kompaktní i jagged)
pro přístup k ostatním kolekcím je možné využít standardní objektové rozhraní (např. ve stylu C#) open System.Collections.Generic let myList = new List<string>() myList.Add("hello") myList.[0]
Srovnání .NET a F# kolekcí .NET
Insert
Remove
Lookup
F# counterpart
List
O(1) / O(n)*
O(n)
O(n) (linear)
No built-in equivalent
LinkedList
O(1)
O(1)
O(n)
No built-in equivalent
Stack
O(1)
O(1)
O(n)
List
Queue
O(1)
O(1)
O(n)
No built-in equivalent
HashSet
O(1) / O(n)*
O(1)
O(1)
Dictionary
O(1) / O(n)*
O(1)
O(1)
převzato z Wikibooks (F#)
Insert
Remove
Lookup
O(1)
n/a
O(n)
Set
O(log n)
O(log n)
O(log n)
Map
O(log n)
O(log n)
O(log n)
Třídy
z hlediska F# jsou třídy typy definované pomocí konstruktoru kontext objektu je de facto uzávěrem kontextu konstruktoru (viz syntaxe), v tomto kontextu jsou vázány datové členy (u běžných nelze již vazbu změnit) definice třídy (implicitní zápis, existuje ještě explicitní)
type Account(number : int, holder : string) = class let mutable amount = 0m member x.Number = number member x.Holder = holder member x.Amount = amount
end
member x.Deposit(value) = amount <- amount + value member x.Withdraw(value) = amount <- amount - value
Použití tříd
použití tříd se v zásadě neliší v C#, objekty však lze využívat i v nativních F# konstrukcích
let transfer amount (src : Account) (trgt : Account) = src.Withdraw amount trgt.Deposit amount //převzato z Wikibooks let (|Debet|Kredit|) (a : Account) = if a.Amount < 0m then Debet(a.Amount) else Kredit(a.Amount) let loan = function | Debet _ -> 1000m | Kredit m -> m/2m let a1 = new Account(666, "Sauron") a1.Deposit(1200000) loan a1
Monády
monády jsou funkcionálním prostředkem pro implementaci specializovaných toků řízení poznámka: běžným tokem se rozumí typický funkcionální neorientovaný strom vyhodnocení! v F# se monády označují jako computation expressions nebo workflows monády využívají běžné funkcionální mechanismy přímé použití však vede k velmi komplikovaným a nepřehledným kódům, proto moderní jazyky nabízejí syntaktické pozlátko: linearizované sekce programu mapované na monády pro pasivní využití monád postačuje jen pochopení relativně jednoduchého modelu tzv. obalených hodnot
Monády --- vnější pohled
hlavní východisko hodnoty se mohou vyskytovat ve dvou základních stavech:
přímé hodnoty mohou být zpracovány běžnými funkcemi (všechny dříve přímé hodnoty) obalené hodnoty lze bezpečně používat v prostředí monády tj. vždy plně podporují její sémantiku obalení je realizováno běžnými prostředky (je to např. seznam, hodnota variant nebo funkce), převod mezi stavy (tj. zabalení a rozbalení) však podléhá striktní sémantice, která monádu izoluje od zbytku jazyka
Monáda multihodnot
jako příklad uveďme monádu, která umožňuje zpracování multihodnot multihodnota je množinou všech potenciálních hodnot (obdoba kvantových superpozic) na multihodnoty lze aplikovat běžné operace, které však mají mírně pozměněnnou sémantiku
operace jsou volány postupně na všechny prvky multihodnoty (= množiny) jednotlivé výsledky tvoří množinu, kterou lze interpretovat jako výsledek (tj. novou multihodnotu)
{1,0} + {2,3,4} = {2,3,4,5}
implementace: Perl 6 a jeho junctions
Použití monády let result = variant { let! x = [2;3] let! y = [5;6;7;10] let! s = [-1;1] let z = 2*x + y return s*(z + 10) }
uvnitř bloku variant lze vidět jak obalené hodnoty (seznamy převoditelné na množiny) tak výrazy s hodnotami přímými (viz např. výrazy 2*x + y, s*(z + 10) )
vazba pomocí let! hodnoty rozbaluje (tj. symbol následně odkazuje na přímé hodnoty) konstrukce return naopak hodnotu obaluje (jen tak může být předána vně monády (return nevrací hodnotu!)
Jak je to implementováno?
překladač blok variant převede na výraz využívající funkcí bind (zajišťuje volání běžných funkcí na obalené hodnoty) a return (zabalení) funkce bind (převod na množinu, mapování funkce přes a následné sjednocení výsledků): bind boxedx f = boxedx | Set.ofList |> Set.map f |> Set.fold Set.union Set.empty Set<'a> -> ('a -> Set<'b>) -> Set<'b>
funkce return (z prvku vytváří jednoprvkovou množinu) return x = Set.add x Set.empty 'a -> Set<'a>
Rozpis multihodnotové monády
sekvenční blok: variant { let! x [false, true] let! y [false, true] return x || not y }
je nahrazen výrazem (zjednodušeno): bind [true, false], (fun x -> bind [true, false], fun y -> (return x || not y) )
výsledkem je množina s jedinou hodnotou (tj. logický výraz je tautologie)
Skutečná implementace
skutečná implementace je složitější, neboť překladač potřebuje implementovat monádu jako objekt přesněji: monáda je singleton vytvořený továrnou (zde je to přímo třída) type VariantBuilder() = class member this.Bind(x, f) = setflatmap f (Set.ofList x) member this.Return(x) = toSet x member this.Delay(f) = f() //u jedn. monád vždy stejné end let variant = VariantBuilder() //vytvoření singletonu
Příklady monád
serializační monády, které vynucují postupné provádění funkcí (tj. tvoří procedurální ostrov ve čistě fukcionálním jazyce) Haskell: tzv. IO monády F#: nepoužívají se (jazyk není čistě funkcionální) maybe monáda --- pracuje nativně s hodnotami typu option. Pokud v toku zpracování vznikne hodnota none, pak se automaticky vrací None (další operace se již neprovádí) async workflow --- jednotlivé operace jsou vykonávány asynchronně (a potenciálně i paralelně) jako úlohy nad množinou vláken. Monáda automaticky zajišťuje i synchronizaci.
