Úvod do jazyka Reason: funktory

Jednoduché použití modulů

Chceme naprogramovat datovou strukturu množina. Modul implementující množinu bude mít následující rozhraní:

module type MySetInterface = {
  type t('a);
  let empty : t('a);

  let add : 'a => t('a) => t('a);

  let mem : 'a => t('a) => bool;
};

Typ t('a) sloužít k reprezentaci množiny prvků typu 'a. Typ t je generický, 'a zastupuje libovolný typ prvků v množině. Funkce empty vrátí prázdnou množinu. Funkce add přidá do množiny prvek a vrací novou množinu. Funkce mem vrací, zda prvek je v množině.

Množina může být implementována pomocí binárních vyhledávacích stromů:

module MySet: MySetInterface = {
  type t('a) =
    | Fork(t('a), 'a, t('a))
    | Leaf;
  let empty = Leaf;
  let rec add = (x, node) =>
    switch node {
    | Fork(left, value, right) =>
      let i = compare(value, x);
      /* value in the current node is smaller than x - insert into left subtree */
      if (i < 0) {
        Fork(add(x, left), value, right)
      } else if (i > 0) {
        Fork(left, value, add(x, right))
      } else {
        node
      }
    | Leaf => Fork(Leaf, x, Leaf)
    };
  let rec mem = (x, node) =>
    switch node {
    | Fork(left, value, right) =>
      let i = compare(value, x);
      /* value in the current node is smaller than x */
      if (i < 0) {
        mem(x, left)
      } else if (i > 0) {
        mem(x, right)
      } else {
        true
      }
    | Leaf => false
    };
};

Implementace binárních vyhledávacích stromů porovnává hodnoty typu 'a pomocí funkce compare. compare je speciální funkce ze standardní knihovny typu 'a => 'a => int. Funkce compare tedy zdánlivě funguje s libovolným typem 'a. Například pro řetězce:

let stringSet = MySet.add("Root.cz", MySet.empty);
Js.log(MySet.mem("Root.cz", stringSet));

Ve skutečnosti však existuje řada typů, kde funkce compare nefunguje. compare například neumí porovnat funkce:

let pairSet = MySet.add(((x) => x + 1, 17), MySet.empty);
Js.log(MySet.mem(((x) => x + 1, 17), pairSet));

Výše uvedený kód vyhodí výjimku. Pokud bychom chtěli do naší množiny ukládat dvojice (funkce, číslo), nesmíme používat funkci compare ze standardní knihovny.

Nejjednodušší řešení je předat vlastní compare explicitně každé funkci, která doposud volala knihovní  compare:

module type MySetInterfaceExplicit = {
  type t('a);
  let empty : t('a);

  let add : (~compare:(('a, 'a) => int), 'a, t('a)) => t('a);

  let mem : (~compare:(('a, 'a) => int), 'a, t('a)) => bool;
};

Nevýhodou tohoto řešení je, že kompilátor již nehlídá, zda pokaždé předáváme stejný compare. Například, zda množinu nenaplníme pomocí jedné funkce compare a pak funkci mem nepředáme jiný compare. Druhou nevýhodou je hůře čitelný kód – balast u každého volání funkcí mem a  add.

Další možností je předat compare při vytváření prázdné množiny a uložit ho přímo v datové struktuře. Tímto přijdeme o některé optimalizace kompilátoru a každou strukturu zvětšíme o jednu referenci na  compare.

Funktory

Řešením našich problémů je pro každý compare vytvořit novou implementaci množiny, celý modul MySet specializovaný pro daný compare. Nechceme však kopírovat kód. Používaným řešením jsou funktory – jakési funkce, jež na vstupu dostávají modul(y) a vrací modul.

Množinu tedy budeme realizovat jako funktor, který dostane modul s funkcí compare, jenž funguje pro jeden pevně daný typ (není generická), a vrátí implementaci množiny pro tento konkrétní typ.

Začneme tím, že popíšeme rozhraní vstupního modulu. Jelikož funkce compare bude pracovat s jedním konkrétním typem, nebude generická, tak rozhraní nemůže vypadat takhle:

module type ComparableBad = {
  let compare: 'a => 'a => bool
};

Toto rozhraní je špatně, protože požaduje generickou funkci compare, tu ale nejde rozumně naimplementovat. Nemůžeme však psát ani

module type ComparableBad2 = {
  let compare: string => string => int
};

neb tato verze compare může pracovat pouze na řetězcích, naše množiny by tak mohly obsahovat pouze řetězce, což je nepřípustné omezení. My potřebujeme takové rozhraní modulu, kterému bude odpovídat modul s funkcí compare porovnávající řetězce, ale i modul s funkcí compare porovnávající dvojice, ale i modul s funkcí compare porovnávající libovolný pevně daný typ. Takové rozhraní vytvoříme pomocí abstraktního typu

module type Comparable = {
  type t;
  let compare: t => t => int
};

Comparable.t je typ, s kterým Comparable.compare umí pracovat. Zde jsou příklady modulů s tímto rozhraním:

module StringComparable = {
  type t = string;
  let compare = compare;
};

module PairComparable = {
  type t = (int => int, string);
  let compare = ((_, a), (_, b)) => compare(a, b);
};

První modul je pro porovnávání řetězců, druhý modul je pro dvojice. Nyní vytvoříme funktor MakeMySet, který přijímá moduly s rozhraním Comparable a vrací moduly s rozhraním MySetInterface, kde abstraktní typ value nahradíme konkrétním typem z rozhraní Comparable (bez použití konstrukce with by typ value zůstal abstraktní a množina by se prakticky nedala použít; vyzkoušejte si to!):

module type MySetInterface = {
  type value;
  type t;
  let empty : t;

  let add : value => t => t;

  let mem : value => t => bool;
};

module MakeMySet = (C: Comparable) : (MySetInterface with type value = C.t) => {
  type value = C.t;
  type t =
    | Fork(t, value, t)
    | Leaf;
  let empty = Leaf;
  let rec add = (x, node) =>
    switch node {
    | Fork(left, value, right) =>
      let i = C.compare(value, x);
      /* value in the current node is smaller than x - insert into left subtree */
      if (i < 0) {
        Fork(add(x, left), value, right)
      } else if (i > 0) {
        Fork(left, value, add(x, right))
      } else {
        node
      }
    | Leaf => Fork(Leaf, x, Leaf)
    };
  let rec mem = (x, node) =>
    switch node {
    | Fork(left, value, right) =>
      let i = C.compare(value, x);
      /* value in the current node is smaller than x */
      if (i < 0) {
        mem(x, left)
      } else if (i > 0) {
        mem(x, right)
      } else {
        true
      }
    | Leaf => false
    };
};

Aplikací funktoru na moduly s porovnávacími funkcemi vytvoříme moduly pro množiny:

module MyStringSet = MakeMySet(StringComparable);
module MyPairSet = MakeMySet(PairComparable);

Použití množin je snadné:

let pairSet = MyPairSet.add(((x) => x + 1, "foo"), MyPairSet.empty);
Js.log(MyPairSet.mem(((x) => x + 1, "foo"), pairSet));

Řada datových struktur ve standardní knihovně je k dispozici ve formě funktorů:

• Množina a funktor Set.Make.
• Mapa a funktor Map.Make.
• Hešovací tabulka a funktor Hashtbl.Make.

Nyní už je umíme používat.

Polymorfní varianty

V příštím díle se budeme zabývat polymorfními variantami, objekty a řádkovým polymorfismem, který se v Reasonu používá místo klasického podtypového polymorfismu kvůli snazší typové inferenci.