Zajímalo mě, jak lze datové struktury implementovat čistě funkcionálně, tedy při podmínce, že nemám k dispozici nic víc než funkce, closury a primitiva. Otevřel se mi nový svět…

Closure

function lazyIncrement(start) {
  return function() {
    return start++;
  }
}

///
var g = lazyIncrement(2);
g();// 2
g();// 3
g();// 4

Closury jsou funkce, které si pamatují stav prostředí, ve kterém byly vytvořeny. Nám přesně kvůli této vlastnosti poslouží jako start pro implementaci čistě funkcionálních datových struktur.

Linked list

Jelikož nemáme vůbec nic, musíme začít od základu. Základem bude linked list, základní datová struktura tolik typická pro LISP, která je perzistentní a neměnná. Přidám-li element na začátek seznamu, pak nejenže se původní list nijak nezmění, ale nový list bude bezpečně sdílet většinu s listem původním, což šetří místo.

--------   --------   --------
| 1 | ---> | 2 | ---> | 3 | null
--------   --------   --------

cons       cons       cons
car cdr

Článek listu (cons) obsahuje car (v tomto případě hodnotu) a cdr, což je ukazatel na článek následující, nebo null v případě, že tímto článkem list končí:

var cons = function(car, cdr) {
  return function(list) {
    return list(car, cdr);
  };
};

///
var list = cons('a', cons('b', cons('c', null)));

Abychom mohli s listem pracovat, musíme definovat funkce car a cdr, které z listu dostanou hodnotu car respektive cdr:

var car = function(list) {
  if (list === null) return null;
  return list(function(p, q) {
    return p;
  });
};

var cdr = function(list) {
  if (list === null) return null;
  return list(function(p, q) {
    return q;
  });
};

///
car(list);// 'a'
cdr(list);// cons('b', cons('c', null))

Pojďme použít list v praxi a řekněme, že potřebujeme najít element v listu podle predikátu:

var find = function(list, predicate) {
  if (list === null) return null;
  return predicate(car(list)) ? car(list) : find(cdr(list), predicate);
};

///
find(cons(5, cons(6, cons(7, null))), function(x) { return x % 2 === 0; });// 6

S rekurzí se ve funkcionálním programování setkáte velice často. Ale pozor, při intenzivní rekurzi (například kdybyste hledali nad listem o x tisících elementech) může dojít k přetečení stacku. Obejít se to dá buď cyklem… nebo tzv. tail call optimalizací. Lepší jazyky touto dovedností oplývají, javascript se jí snad jednou také dočká.

Queue

Než se pustíme do implementace další datové struktury, musíme nadefinovat dvě funkce pro manipulaci s linked listem. Ani jednu není třeba představovat:

var reverse = function(list) {
  if (list === null) return null;
  return (function $(list, reversed) {
    var rest = cdr(list);
    reversed = cons(car(list), reversed);
    return rest === null ? reversed : $(rest, reversed);
  })(list, null);
};

var size = function(list) {
  if (list === null) return 0;
  return (function $(list, length) {
    var rest = cdr(list);
    return rest === null ? length : $(rest, length + 1);
  })(list, 1);
};

///
var list = cons('a', cons('b', null));
reverse(list);// cons('b', cons('a', null))
size(list);// 2

Queue, česky frontu známou také jako FIFO jsem jako dalšího adepta na implementaci nevybral náhodou. Klasicky mutabilně ji lze řešit následovně pomocí pole:

var queue = [];
queue.push('a');  // (void 0)  ['a']
queue.push('b');  // (void 0)  ['a', 'b']
queue.shift();    // 'a'       ['b']

Metoda shift nejenže vrací nejdříve přidaný element, ale zároveň mutuje původní queue. To má za výsledek to, že když zavoláte shift dvakrát, dostanete dva různé výsledky.

Přesně tomuto chování musíme v čistě funkcionálních strukturách zabránit. Funkce shift proto nebude vracet první element, ale novou frontu bez právě toho prvního elementu. Obdobně se bude chovat funkce push, která bude vracet frontu novou, obohacenou o jeden element přidaný na konec. Pro jednoduchý přístup k hodnotě (té, co vrací metoda shift) použijeme funkci head.

Queue sestavíme z několika linked listů. Jeden, hlavní, bude představovat samotnou frontu - odkaz na front list a odkaz na rear list:

var queue = function(front, rear) {
  return size(front) === 0 ? cons(reverse(rear), null) : cons(front, rear);
};

var shift = function(q) {
  if (car(q) === null || cdr(q) === null) null;
  return queue(cdr(car(q)), cdr(q));
};

var push = function(q, x) {
  return queue(car(q), cons(x, cdr(q)));
};

// pomocná funkce pro získání hodnoty z queue
var head = function(q) {
  return car(car(q));
};

///
var emptyQueue = queue(null, null);
var queueWithTwoElements = push(push(queue, 'a'), 'b');
head(queueWithTwoElements);// 'a'
head(shift(queueWithTwoElements));// 'b'

Zajímá-li vás, proč je fronta implementována zrovna pomocí dvou listů, pak můžete šáhnout po skvělé knize o funkcionálních datových strukturách od Chrise Okasakiho, kde je vše popsáno a vysvětleno. Kniha obsahuje nejen elegantní implementaci (především díky pattern-matchingu v Haskellu!), ale i potřebnou matematickou teorii.

Další zdroje informací: