Rekurze a pattern matching v programovacím jazyku F#

Obsah

1. Rekurzivní funkce

2. Přímá rekurze

3. Nepřímá rekurze

4. Rekurzivní funkce odd i even?

5. Korektní zápis nepřímé rekurze

6. Koncová rekurze

7. Pattern matching

8. Rekurzivní výpočet Fibonacciho posloupnosti s pattern matchingem

9. Rekurzivní výpočet faktoriálu s pattern matchingem

10. Kontrola neplatného vstupu v bloku match

11. Pattern matching pro větší množství hodnot

12. Rekurzivní implementace Ackermannovy funkce

13. Kontrola neplatných vstupních hodnot pro Ackermannovu funkci

14. Získání zvoleného prvku z n-tice s využitím pattern matchingu

15. Test nulovosti souřadnice, opět založeno na pattern matchingu

16. Přečtení zvoleného prvku ze záznamu (record), opět s využitím pattern matchingu

17. Obsah navazujícího článku

18. Repositář s demonstračními příklady

19. Literatura

20. Odkazy na Internetu

1. Rekurzivní funkce

Ve funkcionálních jazycích, mezi něž F# patří (i když se nejedná o čistě funkcionální jazyk), se velmi často setkáme s rekurzivními funkcemi, typicky založenými na principu postupného zjednodušování problému. Rekurze může být přímá, což znamená, že v nějaké funkci voláme tu samou funkci (ovšem typicky s rozdílnými parametry) nebo nepřímá, kdy například funkce A volá funkci B a ta ve svém těle volá opět funkci A. V praxi se pochopitelně v obou variantách nesmí zapomenout na podmínku zajišťující ukončení rekurze.

V programovacím jazyku F# se tyto dvě formy rekurze rozlišují už na syntaktické úrovni, jak to ostatně uvidíme na demonstračních příkladech. A navíc rozlišujeme ještě takzvanou koncovou rekurzi (přímou či nepřímou), kdy posledním příkazem funkce je rekurzivní zavolání té samé funkce, popř. jiné funkce (ovšem nesmí se jednat o součást složitějšího výrazu). Takovou formu rekurze je možné optimalizovat a vlastně ji interně převést na programovou smyčku. V navazujících kapitolách si jednotlivé formy rekurze ukážeme na demonstračních příkladech.

2. Přímá rekurze

Pro ukázku toho, jakým způsobem lze naprogramovat funkci s přímou rekurzí, se podívejme na následující pokus o definici funkce určené pro výpočet Fibonacciho posloupnosti. Samotný způsob výpočtu je prakticky bez změn převzat z matematické definice této funkce. Tělo funkce je proto snadno pochopitelné – pro hodnoty 0 a 1 se vrací přímo tyto hodnoty (a tím se rekurze ukončí) a pro hodnoty větší nebo rovny dvěma se rekurzivně volá ta samá funkce s parametrem n-1 a n-2:

let fib n =
  if n < 2 then
    n
  else
    fib (n - 1) + fib (n - 2)
;;
 
printf "%d" (fib 10)

Ovšem při pokusu o překlad (a zavolání) této funkce vypíše překladač chybu:

The value or constructor 'fib' is not defined.

Proč tomu tak je? V průběhu deklarace funkce ještě skutečně není symbol fib definován, protože výraz s let není ukončen (dvojicí středníků). Proto překladač správně napsal, že tento symbol nemůže použít.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/recursion1.fs.

Řešení tohoto problému spočívá v tom, že překladači dopředu napovíme, že deklarujeme rekurzivní funkci. Tato nápověda spočívá ve vložení klíčového slova rec před jméno funkce:

let rec fib n =
  if n < 2 then
    n
  else
    fib (n - 1) + fib (n - 2)
;;
 
printf "%d" (fib 10)

Nyní již bude překlad a zavolání této funkce provedeno bez problémů.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/recursion2.fs.

Z výše uvedené poznámky taktéž vyplývá, proč je následující zápis plně korektní, i když se v něm nedefinuje rekurzivní funkce, ale funkce „obyčejná“ – slovo rec nepřidává žádné další „vlastnosti“ k deklarované funkci, ale pouze definuje nový symbol s lokálním rozsahem:

let rec add x y = x + y
 
printf "%d" (add 1 2)

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/recursion4.fs.

3. Nepřímá rekurze

Nepřímá rekurze znamená, že nějaká funkce A volá funkci B a naopak ve funkci B se za určité podmínky volá funkce A (a podobně lze tuto konstrukci rozšířit na více funkcí, které se vzájemně volají, například ve stylu A→B→C→A). Nepřímá rekurze sice může na první pohled vypadat jako poměrně umělá (čti nepraktická) konstrukce, ale nalezneme ji například v klasickým min-max algoritmech použitých ve hrách apod.

Pokusme se nyní napsat program, který zjistí, zda je celočíselná hodnota sudým nebo lichým číslem. Myšlenka, na které je celý algoritmus postaven, může být následující – dokážeme rozlišit pouze 0 (sudá hodnota) a 1 (lichá hodnota); sudost/lichost dalších hodnot zjistíme rekurzivně za předpokladu, že:

sudá x → lichá x-1
lichá x → sudá x-1

První „nástřel“ implementace tohoto algoritmu může vypadat následovně:

let even x =
  if x = 0
  then true
  else odd (x-1)
 
let odd x =
  if x = 0
  then false
  else even (x-1)
 
 
printf "%b" (even 1)
printf "%b" (even 2)
printf "%b" (even 3)
printf "%b" (even 4)

Překladač ovšem při pokusu o překlad první funkce even vypíše chybové hlášení o tom, že nezná (pochopitelně) funkci odd:

The value or constructor 'odd' is not defined.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/odd_even₁.fs.

4. Rekurzivní funkce odd i even?

V případě, že bychom přesně nevěděli, jaký význam má klíčové slovo rec, mohli bychom předpokládat, že program z předchozí kapitoly postačuje triviálně upravit následujícím způsobem:

let rec even x =
  if x = 0
  then true
  else odd (x-1)
 
let rec odd x =
  if x = 0
  then false
  else even (x-1)
 
 
printf "%b" (even 1)
printf "%b" (even 2)
printf "%b" (even 3)
printf "%b" (even 4)

Ve skutečnosti ani toto ovšem není korektní zápis, protože zápis s rec pouze znamená, že uvnitř funkce odd bude možné použít symbol odd a uvnitř funkce even lze použít symbol even. Žádné další záruky ani nové možnosti toto klíčové slovo nenabízí.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/odd_even₂.fs.

5. Korektní zápis nepřímé rekurze

Jediný korektní způsob zápisu nepřímé rekurze vyžaduje společnou deklaraci obou funkcí, které se vzájemně volají. Obě deklarace se spojují – což může být zpočátku poněkud matoucí – s využitím klíčového slova and. A pochopitelně je nutné použít klíčové slovo rec, které zajistí, že se interně (při deklaraci obou funkcí) mohou používat symboly even a odd. Výsledek by měl vypadat následovně:

let rec even x =
  if x = 0
  then true
  else odd (x-1)
and odd x =
  if x = 0
  then false
  else even (x-1)
 
 
printf "%b" (even 1)
printf "%b" (even 2)
printf "%b" (even 3)
printf "%b" (even 4)

Tento program po svém překladu a spuštění vypíše:

false
true
false
true

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/odd_even₃.fs.

Mohlo by se zdát, že můžeme vynechat klíčové slovo rec, protože ve funkci even se tato funkce nevolá a podobně je tomu i u funkce odd (nepřímá rekurze). Jenže v deklaraci funkce even je nutné použít symbol odd a v deklaraci funkce odd naopak voláme even, takže rec je povinné a vztahuje se na obě funkce (či na více funkcí) deklarované společně.

Dokonce při vynechání rec může překladač ohlásit hned několik chyb a varování:

let even x =
  if x = 0
  then true
  else odd (x-1)
and odd x =
  if x = 0
  then false
  else even (x-1)
 
 
printf "%b" (even 1)
printf "%b" (even 2)
printf "%b" (even 3)
printf "%b" (even 4)

Překladač v tomto případě vypíše několik varování (či doporučení) a chyb:

The declaration form 'let ... and ...' for non-recursive bindings is not used in F# code. Consider using a sequence of 'let' bindings(20,1)
The value or constructor 'odd' is not defined.(23,8)
The value or constructor 'even' is not defined. Maybe you want one of the following:

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/odd_even₄.fs.

6. Koncová rekurze

Připomeňme si, že pokud je posledním příkazem v nějaké rekurzivní funkci volání té samé funkce, říkáme, že se jedná o koncovou rekurzi (tail recursion). Takový zápis rekurze dokáže překladač nahradit za programovou smyčku, která se pochopitelně vyhodnocuje rychleji, než skutečná rekurze (odpadá předávání parametrů přes zásobník a vlastní volání funkce). Ovšem například náš původní algoritmus výpočtu členu Fibonacciho posloupnosti sice rekurzivně volá sebe samu, ale ne v tail pozici a tudíž se nejedná o koncovou rekurzi (kromě rekurzivního volání funkce se navíc provádí další volání a výsledek obou volání se sčítá – tudíž se jedná o nějakou formu paměti):

let rec fib n =
  if n < 2 then
    n
  else
    fib (n - 1) + fib (n - 2)
;;
 
printf "%d" (fib 10)

Abychom mohli využít všech výhod koncové rekurze, je nutné program upravit. Vytvoříme si pomocnou lokální funkci, které se namísto jednoho parametru předávají tři parametry, přičemž první parametr bude počitadlem a druhé dva parametry představují členy n a n+1. Vlastně explicitně říkáme, jaké proměnné (či parametry) jsou nutné v každém kroku iterace. Výsledná interní funkce tailr je zapsána tak, že se rekurzivní volání nachází v tail pozici a tudíž překladač bude moci použít smyčku:

let fib n =
  let rec tailr i a b =
    if i = 0 then a else tailr (i-1) b (a + b)
  in
  tailr n 0 1;;
 
printf "%d" (fib 10)

Obecně lze říci, že přepis výpočtu na koncovou rekurzi prakticky vždy vyžaduje pomocné parametry, které slouží jako akumulátory vypočtených mezivýsledků.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/recursion3.fs.

7. Pattern matching

Velmi důležitým konceptem, který byl rozvinut v programovacím jazyku ML i v jeho následovnících (kam nepochybně patří i F#), je takzvaný pattern matching neboli rozpoznávání vzorů. Tato technika byla později s menšími či většími úpravami převzata i do dalších programovacích jazyků, například do Rustu nebo nověji taktéž do Pythonu. V navazujících kapitolách se podíváme na způsoby využití této programovací techniky.

Připomeňme si, že v původním jazyku ML vypadal zápis funkce s pattern matchingem následovně:

fun <jméno> <vzorek> = <tělo/výraz>

Většinou se však používá větší množství vzorků, které jsou spojeny znakem „or“ (pipe, svislá čára). V takovém případě jsou vzorky postupně procházeny a pokud budou vyhovovat předaným datům, bude příslušná větev funkce vykonána:

fun <jméno> <vzorek> = <tělo/výraz>
 |  <jméno> <vzorek> = <tělo/výraz>
 |  <jméno> <vzorek> = <tělo/výraz>
 |  <jméno> <vzorek> = <tělo/výraz>

Příkladem může být rekurzivní výpočet Fibonacciho posloupnosti. Varianta výpočtu bez využití pattern matchingu by vypadala takto:

(* Naivní implementace výpočtu Fibonacciho posloupnosti *)
 
fun fib n =
    if n = 0 then 0 else
    if n = 1 then 1 else
    fib (n - 1) + fib (n - 2);

Ve skutečnosti ovšem můžeme vzít matematický předpis a prakticky doslova ho přepsat do ML:

(* Implementace výpočtu Fibonacciho posloupnosti s využitím pattern matchingu *)
 
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2);

8. Rekurzivní výpočet Fibonacciho posloupnosti s pattern matchingem

Vraťme se nyní k hlavnímu tématu tohoto článku – k programovacímu jazyku F#. V tomto jazyku lze pattern matching použít při výpočtu Fibonacciho posloupnosti následovně:

let rec fib = function
    0 -> 0
  | 1 -> 1
  | n -> fib (n-1) + fib (n-2)
 
printf "%d" (fib 20)

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/fibonacci1.fs.

Alternativně lze použít i tento (více idiomatický) zápis založený na použití klíčového slova match a with:

let rec fib n =
  match n with
    0 -> 0
  | 1 -> 1
  | n -> fib (n-1) + fib (n-2)
 
printf "%d" (fib 20)

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/fibonacci2.fs.

9. Rekurzivní výpočet faktoriálu s pattern matchingem

Prakticky stejným způsobem můžeme realizovat i algoritmus výpočtu faktoriálu. Opět se při výpočtu budeme rozhodovat mezi třemi větvemi tak, jak to odpovídá rekurzivní definici faktoriálu:

let rec factorial n =
    match n with
    | 0 -> 1
    | 1 -> 1
    | _ -> n * factorial(n-1)
 
printf "%d" (factorial 10)

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/pattern1.fs.

Ovšem povšimněte si, že výsledek první a druhé větve je totožný. V takovém případě můžeme oba vzory (pattern) zapsat na jeden řádek a oddělit je pomocí znaku | tak, jak je to naznačeno níže. Výsledek je možná méně čitelný, ale na druhou stranu je kratší (zejména tehdy, pokud by se provádět složitější výpočet; zde pouze vracíme hodnotu 1):

let rec factorial n =
    match n with
    | 0 | 1 -> 1
    | _ -> n * factorial(n-1)
 
printf "%d" (factorial 10)

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/pattern2.fs.

10. Kontrola neplatného vstupu v bloku match

Naše funkce pro výpočet faktoriálu trpí jednou vadou – nebude funkční pro záporné hodnoty n (sami si odpovězte, co se v tomto případě stane?). Ovšem výpočet lze relativně snadno upravit do podoby, v níž se kontroluje, zda je n záporné. Pokud tomu tak je, vyhodíme výjimku (což je téma, kterému se dnes ještě nechci věnovat do podrobností). Co nás ale bude zajímat – jak se zapíše podmínka v bloku založeného na pattern matchingu? K tomuto účelu lze použít zápis s when, kterým vlastně říkáme „pro každé n menší než nula …“. Upravený výpočet může vypadat takto:

let rec factorial n =
    match n with
    | n when n < 0 -> invalidArg "input" "non-negative integer expected"
    | 0 | 1 -> 1
    | _ -> n * factorial(n-1)
 
printf "%d" (factorial 10)
printf "%d" (factorial -10)

Povšimněte si, že z prvního řádku v bloku match se nevrací žádná hodnota, což však internímu algoritmu pro pattern matching nevadí, protože správně odvodí, že tato funkce vrací hodnotu typu int.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/pattern3.fs.

11. Pattern matching pro větší množství hodnot

Technologii pattern matchingu můžeme použít nejenom pro jedinou kontrolovanou hodnotu (v předchozích příkladech se jednalo o n), ale i pro větší množství hodnot. Podívejme se například na jednu z možných implementací funkce pro výpočet největšího společného dělitele (to je ostatně další oblíbená školní úloha). Tato funkce má dva parametry a oba parametry můžeme testovat současně. Pokud je druhý parametr nulový, je výpočet u konce a můžeme vrátit hodnotu prvního parametru. Pokud není nulový, zavoláme rekurzivně tutéž funkci, nyní ovšem s parametry b a a % b. Zápis této funkce je tedy poměrně dobře pochopitelný:

let rec gcd a b =
    match a, b with
    | (a,0) -> a
    | (a,b) -> gcd b (a % b)
 
 
printf "%d" (gcd 12 8)
printf "%d" (gcd 168 180)

Po překladu a spuštění tohoto příkladu získáme správné výsledky:

4
12

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/pattern4.fs.

12. Rekurzivní implementace Ackermannovy funkce

Prakticky stejným způsobem, jen s odlišnými větvemi a výrazy, můžeme realizovat rekurzivní výpočet Ackermannovy funkce. Tato funkce není primitivně rekurzivní a tudíž se nedá přepsat do podoby s tail pozicemi a tedy do podoby, v níž může překladač nahradit rekurzivní volání za programovou smyčku. Nyní nás však bude zajímat především podoba bloku match, která prakticky přesně odpovídá definici Ackermannovy funkce (pouze v případě vzorů nelze použít n-1, takže jsou všechny parametry posunuté o jedničku):

let rec ackermann m n =
  match m, n with
  | (0,n) -> n+1
  | (m,0) -> ackermann (m-1) 1
  | (m,n) -> ackermann (m-1) (ackermann m (n-1))
 
printf "%d" (ackermann 2 10)

Výsledek výpočtu by měl být 23.

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/pattern5.fs.

13. Kontrola neplatných vstupních hodnot pro Ackermannovu funkci

I pro parametry Ackermannovy funkce platí určitá omezení – musí se jednat o nulové hodnoty či o kladná čísla. Proto můžeme výpočet upravit do takové podoby, aby se otestovalo, zda není jeden z parametrů záporný. Jedna z možných realizací této kontroly by mohla vypadat následovně (opět tedy použijeme klíčové slovo when, za kterým následuje podmínka):

let rec ackermann m n =
  match m, n with
  | (m,n) when m < 0 || n < 0 -> invalidArg "input" "Ackermann's function is only defined over the non-negative integers"
  | (0,n) -> n+1
  | (m,0) -> ackermann (m-1) 1
  | (m,n) -> ackermann (m-1) (ackermann m (n-1))
 
printf "%d" (ackermann 2 10)
printf "%d" (ackermann -2 10)

Zdrojový kód tohoto demonstračního příkladu naleznete na adrese https://github.com/tisnik/f-sharp-examples/tree/master/arti­cle₀₃/pattern6.fs.

14. Získání zvoleného prvku z n-tice s využitím pattern matchingu

Pattern matching je možné využít (a jak uvidíme v navazujících kapitolách, tak i zneužít) i pro mnoho dalších operací. Podívejme se například na funkci, která akceptuje dvojici (tedy specifickou formu n-tice) a vrátí první prvek z této dvojice:

let first tuple =
  match tuple with
  | (x,_) -> x
 
printf "%d" (first (1,2))

Povšimněte si typu této funkce:

val first : 'a * 'b -> 'a = <fun>

Co to znamená – funkce akceptuje dvojice prvků libovolného typu a současně určuje, že se vrátí hodnota stejného typu, jaký má první prvek dvojice.

Naprosto stejným způsobem můžeme pochopitelně napsat funkci, která vrátí druhý prvek:

let second tuple =
  match tuple with
  | (_,y) -> y
 
printf "%d" (second (1,2))

Nebo si můžeme nechat vrátit dvojici, ovšem s prohozenými prvky:

let swap tuple =
  match tuple with
  | (x,y) -> (y,x) ;;

Typ této funkce napovídá, jaká operace se provádí:

val swap : 'a * 'b -> 'b * 'a =

15. Test nulovosti souřadnice, opět založeno na pattern matchingu

Ukažme si na závěr nějaké příklady na určité zneužití pattern matchingu. Můžeme si vytvořit funkci, která zjistí, zda je alespoň jedna souřadnice (z dvojice souřadnic v rovině) nulová. Budeme tedy hledat takové dvojice, které obsahují hodnoty (0,0), (0, něco jiného) nebo (něco jiného, 0). Pokud budeme chtít použít pattern matching, povede to k následujícímu zápisu:

let zero_coordinate point =
    match point with
    | (0, 0) | (0, _) | (_, 0) -> true
    | _ -> false
 
printf "%b" (zero_coordinate (0, 1))
printf "%b" (zero_coordinate (1, 0))
printf "%b" (zero_coordinate (0, 0))
printf "%b" (zero_coordinate (1, 1))

Typ této funkce je opět odvozen korektně, a to na základě nulových konstant v kódu:

val zero_coordinate : int * int -> bool = <fun>

A nakonec si samozřejmě ukažme výsledky získané po zavolání této funkce pro různé dvojice souřadnic:

true
true
true
false

16. Přečtení zvoleného prvku ze záznamu (record), opět s využitím pattern matchingu

I poslední demonstrační příklad, který si dnes ukážeme, vlastně poněkud zneužívá možnosti nabízené pattern matchingem, ovšem základ tohoto příkladu se může hodit i v reálném programovém kódu. V příkladu deklarujeme nový datový typ record pojmenovaný car:

type car = {
    Color: string;
    Model: string;
    Manufacturer: string;
    Year: int;
}

Dále vytvoříme funkci, která z proměnné (hodnoty) tohoto typu získá pouze označení modelu (povšimněte si způsobu zápisu vzorku):

let get_model car =
  match car with
  {Model = model} -> model

Typ této funkce je opět korektně rozpoznán algoritmem pro odvození typů:

val get_model : car -> string = <fun>

A nyní se můžeme pokusit o zavolání této funkce a zjištění jejího chování:

 
let toyota = {Color="silver"; Model="Corolla"; Manufacturer="Toyota"; Year=1986};;
 
printf "%s" (get_model toyota)

Tento program by měl vypsat:

Corolla

17. Obsah navazujícího článku

V navazující části seriálu o programovacím jazyku F# se budeme zabývat zdánlivě triviálním tématem – datovým typem seznam (list). Ve skutečnosti se však v jazycích odvozených od původního jazyka ML jedná o velmi flexibilní datový typ, pro jehož zpracování (a to včetně pattern matchingu) navíc existují speciální syntaktické prvky.

18. Repositář s demonstračními příklady

Všechny výše popsané demonstrační příklady byly uloženy do repositáře dostupného na adrese https://github.com/tisnik/f-sharp-examples/. V tabulce umístěné pod tímto odstavcem jsou uvedeny odkazy na tyto příklady:

19. Literatura

1. Get Programming with F#
   https://www.manning.com/books/get-programming-with-f-sharp
2. F# for Scientists
   https://www.amazon.com/F-Scientists-Jon-Harrop-ebook/dp/B005PS97RO
3. Domain Modeling Made Functional
   https://fsharpforfunandpro­fit.com/books/
4. Functional Programming with F# (na Overleaf, tedy i se zdrojovými kódy)
   https://www.overleaf.com/pro­ject/5bf2cb3cd9568d5a75bfcb­a9
5. Book of F#
   https://nostarch.com/fsharp
6. F# Programming (Wikibook)
   https://en.wikibooks.org/wi­ki/F_Sharp_Programming
7. Stylish F#: Crafting Elegant Functional Code for .NET and .NET Core
   https://www.amazon.com/dp/1484239997/
8. ML for the Working Programmer
   https://www.cl.cam.ac.uk/~lp15/MLbo­ok/pub-details.html
9. Elements of ML Programming, 2nd Edition (ML97)
   http://infolab.stanford.e­du/~ullman/emlp.html
10. A tour of Standard ML
    https://saityi.github.io/sml-tour/tour/welcome
11. The History of Standard ML
    https://smlfamily.github.i­o/history/SML-history.pdf
12. The Standard ML Basis Library
    https://smlfamily.github.io/Basis/
13. Programming in Standard ML
    http://www.cs.cmu.edu/~rwh/is­ml/book.pdf
14. Programming in Standard ML '97: A Tutorial Introduction
    http://www.lfcs.inf.ed.ac­.uk/reports/97/ECS-LFCS-97–364/
15. Programming in Standard ML '97: An On-line Tutorial
    https://homepages.inf.ed.ac­.uk/stg/NOTES/
16. The OCaml system release 4.13
    https://ocaml.org/releases/4­.13/htmlman/index.html
17. Real World OCaml: Functional programming for the masses
    https://dev.realworldocaml.org/
18. OCaml from the Very Beginning
    http://ocaml-book.com/
19. OCaml from the Very Beginning: More OCaml : Algorithms, Methods & Diversions
    http://ocaml-book.com/more-ocaml-algorithms-methods-diversions/
20. Unix system programming in OCaml
    http://ocaml.github.io/ocamlunix/
21. OCaml for Scientists
    https://www.ffconsultancy­.com/products/ocaml_for_sci­entists/index.html
22. Using, Understanding, and Unraveling The OCaml Language
    https://caml.inria.fr/pub/docs/u3-ocaml/
23. Developing Applications With objective Caml
    https://caml.inria.fr/pub/docs/oreilly-book/index.html
24. Introduction to Objective Caml
    http://courses.cms.caltech­.edu/cs134/cs134b/book.pdf
25. How to Think Like a (Functional) Programmer
    https://greenteapress.com/thin­kocaml/index.html

20. Odkazy na Internetu

1. General-Purpose, Industrial-Strength, Expressive, and Safe
   https://ocaml.org/
2. OCaml playground
   https://ocaml.org/play
3. Online Ocaml Compiler IDE
   https://www.jdoodle.com/compile-ocaml-online/
4. Get Started – OCaml
   https://www.ocaml.org/docs
5. Get Up and Running With OCaml
   https://www.ocaml.org/docs/up-and-running
6. Better OCaml (Online prostředí)
   https://betterocaml.ml/?ver­sion=4.14.0
7. OCaml file extensions
   https://blog.waleedkhan.name/ocaml-file-extensions/
8. First thoughts on Rust vs OCaml
   https://blog.darklang.com/first-thoughts-on-rust-vs-ocaml/
9. Standard ML of New Jersey
   https://www.smlnj.org/
10. Programming Languages: Standard ML – 1 (a navazující videa)
    https://www.youtube.com/wat­ch?v=2sqjUWGGzTo
11. 6 Excellent Free Books to Learn Standard ML
    https://www.linuxlinks.com/excellent-free-books-learn-standard-ml/
12. SOSML: The Online Interpreter for Standard ML
    https://sosml.org/
13. ML (Computer program language)
    https://www.barnesandnoble­.com/b/books/other-programming-languages/ml-computer-program-language/_/N-29Z8q8Zvy7
14. Strong Typing
    https://perl.plover.com/y­ak/typing/notes.html
15. What to know before debating type systems
    http://blogs.perl.org/user­s/ovid/2010/08/what-to-know-before-debating-type-systems.html
16. Types, and Why You Should Care (Youtube)
    https://www.youtube.com/wat­ch?v=0arFPIQatCU
17. DynamicTyping (Martin Fowler)
    https://www.martinfowler.com/bli­ki/DynamicTyping.html
18. DomainSpecificLanguage (Martin Fowler)
    https://www.martinfowler.com/bli­ki/DomainSpecificLanguage­.html
19. Language Workbenches: The Killer-App for Domain Specific Languages?
    https://www.martinfowler.com/ar­ticles/languageWorkbench.html
20. Effective ML (Youtube)
    https://www.youtube.com/watch?v=-J8YyfrSwTk
21. Why OCaml (Youtube)
    https://www.youtube.com/wat­ch?v=v1CmGbOGb2I
22. CSE 341: Functions and patterns
    https://courses.cs.washin­gton.edu/courses/cse341/04wi/lec­tures/03-ml-functions.html
23. Comparing Objective Caml and Standard ML
    http://adam.chlipala.net/mlcomp/
24. What are the key differences between Standard ML and OCaml?
    https://www.quora.com/What-are-the-key-differences-between-Standard-ML-and-OCaml?share=1
25. Cheat Sheets (pro OCaml)
    https://www.ocaml.org/doc­s/cheat_sheets.html
26. Syllabus (FAS CS51)
    https://cs51.io/college/syllabus/
27. Abstraction and Design In Computation
    http://book.cs51.io/
28. Learn X in Y minutes Where X=Standard ML
    https://learnxinyminutes.com/doc­s/standard-ml/
29. CSE307 Online – Summer 2018: Principles of Programing Languages course
    https://www3.cs.stonybrook­.edu/~pfodor/courses/summer/cse307­.html
30. CSE307 Principles of Programming Languages course: SML part 1
    https://www.youtube.com/wat­ch?v=p1n0_PsM6hw
31. CSE 307 – Principles of Programming Languages – SML
    https://www3.cs.stonybrook­.edu/~pfodor/courses/summer/CSE307/L01_SML­.pdf
32. SML, Some Basic Examples
    https://cs.fit.edu/~ryan/sml/in­tro.html
33. History of programming languages
    https://devskiller.com/history-of-programming-languages/
34. History of programming languages (Wikipedia)
    https://en.wikipedia.org/wi­ki/History_of_programming_lan­guages
35. Jemný úvod do rozsáhlého světa jazyků LISP a Scheme
    https://www.root.cz/clanky/jemny-uvod-do-rozsahleho-sveta-jazyku-lisp-a-scheme/
36. The Evolution Of Programming Languages
    https://www.i-programmer.info/news/98-languages/8809-the-evolution-of-programming-languages.html
37. Evoluce programovacích jazyků
    https://ccrma.stanford.edu/cou­rses/250a-fall-2005/docs/ComputerLanguagesChart.png
38. Poly/ML Homepage
    https://polyml.org/
39. PolyConf 16: A brief history of F# / Rachel Reese
    https://www.youtube.com/wat­ch?v=cbDjpi727aY
40. Programovací jazyk Clojure 18: základní techniky optimalizace aplikací
    https://www.root.cz/clanky/pro­gramovaci-jazyk-clojure-18-zakladni-techniky-optimalizace-aplikaci/
41. Moscow ML Language Overview
    https://itu.dk/people/ses­toft/mosml/mosmlref.pdf
42. ForLoops
    http://mlton.org/ForLoops
43. Funkcionální dobrodružství v JavaScriptu
    https://blog.kolman.cz/2015/12/fun­kcionalni-dobrodruzstvi-v-javascriptu.html
44. Recenze knihy Functional Thinking (Paradigm over syntax)
    https://www.root.cz/clanky/recenze-knihy-functional-thinking-paradigm-over-syntax/
45. Currying
    https://sw-samuraj.cz/2011/02/currying/
46. Používání funkcí v F#
    https://docs.microsoft.com/cs-cz/dotnet/fsharp/tutorials/using-functions
47. Funkce vyššího řádu
    http://naucte-se.haskell.cz/funkce-vyssiho-radu
48. Currying (Wikipedia)
    https://en.wikipedia.org/wi­ki/Currying
49. Currying (Haskell wiki)
    https://wiki.haskell.org/Currying
50. Haskell Curry
    https://en.wikipedia.org/wi­ki/Haskell_Curry
51. Moses Schönfinkel
    https://en.wikipedia.org/wi­ki/Moses_Sch%C3%B6nfinkel
52. .NET framework
    https://dotnet.microsoft.com/en-us/
53. F# – .NET Blog
    https://devblogs.microsof­t.com/dotnet/category/fshar­p/
54. Playground: OCaml
    https://ocaml.org/play
55. The F# Survival Guide
    https://web.archive.org/web/20110715231625/htt­p://www.ctocorner.com/fshar­p/book/default.aspx
56. Object-Oriented Programming — The Trillion Dollar Disaster
    https://betterprogramming.pub/object-oriented-programming-the-trillion-dollar-disaster-92a4b666c7c7
57. Goodbye, Object Oriented Programming
    https://cscalfani.medium.com/goodbye-object-oriented-programming-a59cda4c0e53
58. So You Want to be a Functional Programmer (Part 1)
    https://cscalfani.medium.com/so-you-want-to-be-a-functional-programmer-part-1–1f15e387e536
59. So You Want to be a Functional Programmer (Part 2)
    https://cscalfani.medium.com/so-you-want-to-be-a-functional-programmer-part-2–7005682cec4a
60. So You Want to be a Functional Programmer (Part 3)
    https://cscalfani.medium.com/so-you-want-to-be-a-functional-programmer-part-3–1b0fd14eb1a7
61. So You Want to be a Functional Programmer (Part 4)
    https://cscalfani.medium.com/so-you-want-to-be-a-functional-programmer-part-4–18fbe3ea9e49
62. So You Want to be a Functional Programmer (Part 5)
    https://cscalfani.medium.com/so-you-want-to-be-a-functional-programmer-part-5-c70adc9cf56a
63. So You Want to be a Functional Programmer (Part 6)
    https://cscalfani.medium.com/so-you-want-to-be-a-functional-programmer-part-6-db502830403
64. Why Programmers Need Limits
    https://cscalfani.medium.com/why-programmers-need-limits-3d96e1a0a6db
65. Signatures
    https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/signature-files
66. F# for Linux People
    https://carpenoctem.dev/blog/fsharp-for-linux-people/
67. Ionide project
    https://ionide.io/
68. FsAutoComplete
    https://ionide.io/Tools/fsac.html
69. Interactive (.NET for Jupyter Notebook)
    https://github.com/dotnet/in­teractive/#jupyter-and-nteract
70. let Bindings
    https://github.com/dotnet/doc­s/blob/main/docs/fsharp/lan­guage-reference/functions/let-bindings.md
71. Lambda Expressions: The fun Keyword (F#)
    https://github.com/dotnet/doc­s/blob/main/docs/fsharp/lan­guage-reference/functions/lambda-expressions-the-fun-keyword.md
72. Infographic showing code complexity vs developer experience
    https://twitter.com/rossi­pedia/status/1580639227313676288
73. OCaml for the Masses: Why the next language you learn should be functional
    https://queue.acm.org/deta­il.cfm?id=2038036
74. Try EIO
    https://patricoferris.github.io/try-eio/
75. Try OCaml
    https://try.ocaml.pro/
76. ML – funkcionální jazyk s revolučním typovým systémem
    https://www.root.cz/clanky/ml-funkcionalni-jazyk-s-revolucnim-typovym-systemem/
77. Funkce a typový systém programovacího jazyka ML
    https://www.root.cz/clanky/funkce-a-typovy-system-programovaciho-jazyka-ml/
78. Curryfikace (currying), výjimky a vlastní operátory v jazyku ML
    https://www.root.cz/clanky/curryfikace-currying-vyjimky-a-vlastni-operatory-v-jazyku-ml/
79. Operátor J (Wikipedia)
    https://en.wikipedia.org/wi­ki/J_operator
80. Standard ML (Wikipedia)
    https://en.wikipedia.org/wi­ki/Standard_ML
81. Don Syme
    https://en.wikipedia.org/wi­ki/Don_Syme
82. Python to OCaml: Retrospective
    http://roscidus.com/blog/blog/2014/06/0­6/python-to-ocaml-retrospective/
83. Xavier Leroy
    https://en.wikipedia.org/wi­ki/Xavier_Leroy
84. Unit type
    https://en.wikipedia.org/wi­ki/Unit_type