Memoization

Una conseguenza della trasparenza referenziale di una funzione è la possibilità di utilizzare una tecnica detta memoization, che consiste nel mettere in cache risultati di funzioni che hanno un certo costo computazionale. Consideriamo ad esempio la seguente funzione, che calcola il fattoriale di un numero intero:

function factorial(n) {
   let result = 1;
   if (n > 1) {
      result = n * factorial(n - 1);
   }
   return result;
}

Al crescere di n, le risorse richieste per il calcolo del suo fattoriale aumenta. Dal momento che factorial() è una funzione pura e gode quindi della trasparenza referenziale, possiamo sostituire ad una qualsiasi chiamata specifica della funzione il suo risultato.

Prendiamo in cosiderazione quindi la seguente funzione:

function memoize(func) {
   var cache = {};
   return function() {
      var argsAsString = JSON.stringify(arguments);
      cache[argsAsString] = cache[argsAsString] || func.apply(func, arguments);
      return cache[argsAsString];
   };
}

La funzione memoize() prende in input una funzione e restituisce una nuova funzione. Avremo modo di ragionare su questo tipo di funzione più avanti, per il momento ci basta capire qual è il risultato restituito. La funzione restituita prende gli argomenti e li trasforma in stringa in modo da rappresentare una chiave per l'array associativo cache (che, come sappiamo, in JavaScript non è altro che un normale oggetto). In questa cache verranno memorizzati i risultati che via via verranno forniti dall'applicazione della funzione passata come parametro su quegli specifici argomenti. La volta successiva che verrà richiesta l'applicazione della funzione sugli stessi parametri verrà restituito il valore in cache, invece che rieseguire la funzione.

Quindi, nel nostro caso avremo:

var memoizedFactorial = memoize(factorial);
console.log(memoizedFactorial(10)); //risultato: 3628800
console.log(memoizedFactorial(10)); //risultato: 3628800

La prima chiamata alla versione memoizzata del fattoriale eseguirà effettivamente la funzione, mentre dalla seconda chiamata in poi verrà restituito il valore salvato in cache. Da notare come questo semplice meccanismo non può essere applicato a funzioni non pure.