Úvod do jazyka Reason: rekurze

Rekurzivní funkce

Na rozdíl od mnohých programovacíh jazyků standardně v Reasonu nejde používat definované hodnoty (kam spadají i funkce) uvnitř své vlastní definice. Důsledkem je, že standardně nejde definovat rekurzivní funkci:

let repeat = (action, n) =>
  if (n > 0) {
    action();
    repeat(action, n - 1)
  };

Překladač si u rekurzivního volání repeat(action, n - 1) bude stěžovat, že nezná hodnotu  repeat:

The value repeat can't be found 

Příjemným důsledkem tohoto chování v praxi je, že nemusíme vymýšlet nové názvy proměnných:

let x = 7 /* computeSecretNumber() */;
let x =
  switch x {
  | 0 | 1 => 42
  | x => x / 2
  };

x ve switch x je první proměnná x, která má hodnotu 7. Kdyby definované hodnoty byly standardně dostupné uvnitř své definice, tak by x ve switch x byla proměnná, kterou právě definujeme, a k první proměnné, která je již zadefinována, by se nešlo dostat – museli bychom ji pojmenovat jinak např. x' nebo xTmp. Pak ovšem hrozí, že x' nebo xTmp omylem použijeme v dalším kódu místo  x.

Potřebujeme-li definovat rekurzivní funkci, za let přidáme  rec:

let rec repeat = (action, n) =>
  if (n > 0) {
    action();
    repeat(action, n - 1)
  };

Pokud chceme definovat vzájemně rekurzivní funkce, je třeba je definovat naráz (není možné volat funkci, která ještě nebyla definována):

let rec even = (x) => x == 0 || odd (x - 1)
and odd = (x) => x != 0 && even (x - 1);

První funkce je uvozena let rec, další funkce jsou uvozené and, středník je až za poslední funkcí.

Seznamy

Rekurze je velmi užitečná při zpracování rekurzivních datových struktur, například seznamů:

type intList =
  | Nil
  | Cons(int, intList);

Definice typu intList říká, že seznam čísel může mít dva tvary. Buď je to prázdný seznam čísel Nil, nebo je to neprázdný seznam čísel z Cons truovaný z čísla a seznamu čísel.

Seznam s číslem 82 vytvoříme tak, že na začátek prázdného seznamu Nil přidáme číslo 82: Cons(82, Nil). Seznam s čísly 7 a 82 vytvoříme tak, že na začátek seznamu s číslem 82 přidáme číslo  7:

let listWithTwoElements = Cons(7, Cons(82, Nil));

Následuje seznam s čísly 43, 7,  82:

let listWithThreeElements = Cons(43, listWithTwoElements);

Jelikož jsou seznamy čísel neměnné, můžeme bez obav využít seznam listWithTwoElements při definici  listWithThreeElements.

Napišme funkci, která sečte čísla v seznamu:

let rec sum = (list) =>
  switch list {
    | Nil => 0
    | Cons(num, nums) => num + sum(nums)
  };

Prvku na začátku seznamu se říká hlava (anglicky head) a seznamu, který zbyde po utržení hlavy, se říká tělo (anglicky tail). Ve funkci sum je num hlava a nums tělo. Název proměnné pro tělo často volíme jako množné číslo názvu proměnné pro hlavu, například: Cons(item, items) nebo  Cons(x, xs).

Funkce fold

Co se stane, když konstruktory Cons a Nil nahradíme funkcemi? Konkrétně mějme čtyřprvkový seznam

Cons(5, Cons(4, Cons(3, Cons(2, Nil))));

a funkce

let nilS = 0;
let consS = (i, j) => i + j;

Nahrazením dostaneme

consS(5, consS(4, consS(3, consS(2, nilS))));

což je po inlinování funkcí ekvivalentní

5 + 4 + 3 + 2 + 0

Shrnuto: Nahrazením konstruktorů se nám podařilo sečíst čísla v seznamu. Když bychom konstruktory nahradili funkcemi

let nilL = 0;
let consL = (_, j) => 1 + j;

získáme počet prvků v seznamu. Funkce, která nahrazuje konstruktory, se obykle nazývá fold, v případě seznamů často foldRight. Řada užitečných funkcí jde zapsat pomocí funkce  fold:

let rec fold = (cons, nil, list) =>
  switch list {
    | Cons(num, nums) => cons(num, fold(cons, nil, nums))
    | Nil => nil
  };

let length = fold((_, len) => len + 1, 0);
let sum = fold((+), 0);
let map = (f) =>
  fold((num, mappedNums) => Cons(f(num), mappedNums), Nil);
let filter = (cond) =>
  fold((num, filteredNums) => cond(num) ? Cons(num, filteredNums) : filteredNums, Nil);
let existsPositive =
  fold((num, positiveNumberInTail) => num > 0 || positiveNumberInTail, false);

map na každé číslo v seznamu aplikuje funkci f a vrátí nový seznam čísel. filter ponechá v seznamu pouze čísla, která splňují podmínku cond. A existsPositive  otestuje, zda seznam obsahuje kladné číslo. Nevýhodou existsPositive je, že neskončí po nalezení prvního kladného čísla, ale zbytečně bude testovat i všechna čísla po něm. Nejedná se tedy o ekvivalent

cislo1 > 0 || cislo1 > 0 || cislo2 > 0 || ... 

Vtip je v tom, že funkce (||) nevyhodnocuje druhý argument, pokud je první argument true. My jsme však (||) zabalili do naší vlastní funkce (num, positiveNumberInTail) => num > 0 || positiveNumberInTail, která toto chování nesdílí.

Seznamy ze standardní knihovny

Pro zápis seznamů má Reason speciální syntaktickou podporu. Místo

Cons(5, Cons(4, Cons(3, Cons(2, Nil))))

píšeme

[5, 4, 3, 2]

čímž dostaneme seznam typu list(int). Pattern matching provádíme následovně

let rec sum = (list) =>
  switch list {
    | [] => 0
    | [num, ...nums] => num + sum(nums)
  };

Seznamy v Reasonu jsou něco úplně jiného něž pole v JavaScriptu (ačkoliv jejich syntax je stejná):

• Seznamy v Reasonu jsou neměnné.
• Všechny prvky seznamu v Reasonu musí mít stejný typ (jedná se o tzv. homogenní seznamy).
• Časová složitost operací se liší.

Příště

Ukázali jsme si, jak psát rekurzivní funkce a začali jsme se věnovat seznamům. Příště si povíme o tail-rekurzi, o modulu List ze standardní knihovny a funkcích v tomto modulu, které není vhodné používat. Nakonec se dostaneme i k zajímavějším strukturám, než jsou seznamy.