La Transformación de Haskell Curry
y la Aplicación Parcial

2011-08-25 por @joseanpg

La transformación de Schöenfinkel

Moses Schönfinkel descubrió que las funciones de más de una variable pueden expresarse como la composición de funciones de una sola variable. Se lo comunicó a Haskell Curry y curiosamente la historia atribuyó a este último el mérito. Curry jugo limpiamente pero la vida es así. La transformación facilitaba el estudio de los fundamentos de las Matemáticas fundamentales, sí, esas que buscan los simples fundamentos de las "cosas" :)

Veamos como funcionaría dicha transformación en JavaScript. Aunque pueda parecer lo contrario usar una notación un poco más ligera favorece el desarrollo de la cuestión así que en lo que sigue

λ denotará function

ret denotará return

Es solo una notación conveniente. Seguiremos hablando de puro JavaScript, no os asustéis pensando que es algo similar a Haskell.

(Lo lamento por los aficionados a la propuesta de las #-functions, pero aquí puedo elegir y elijo λ ;-)

Bien, consideremos la siguiente función f que tiene toma tres argumentos: 

f = λ(x,y,z){ body }
Obviamente estamos suponiendo que body contiene expresiones que involucran a x,y,z.

Bien, la transformada de Curry [sic] de dicha función será 

g = curry(f) = λ(x){ret λ(y){ret λ(z){body}}}
Observamos que f era una función que tomaba tres argumentos (x,y,z) y devolvía lo que resultase al computar body, pero g es una función que toma un argumento (x) y devuelve otra función de un argumento (y). Veámoslo de nuevo: 
g = curry(f) = λ(x){ret λ(y){ ...}}}

Veamos como funciona la evaluación. Supongamos que queremos evaluar f para 1,2,3. Simple: 

f(1,2,3)
¿Cómo haríamos lo mismo con su g? 
f(1,2,3) = g(1)(2)(3)
Veámoslo despacio. Utilizaré where para indicar los valores que van siendo "clausurados": 
g(1)       = λ(x){ret λ(y){ret λ(z){body}}} where x=1
           = λ(y){ret λ(z){body where x=1}}

g(1)(2)    = λ(y){ret λ(z){body where x=1}} where y=2
           = λ(z){body where x=1, y=2}

g(1)(2)(3) = λ(z){body where x=1, y=2} where z=3
           = body where x=1, y=2, z=3
Resumiendo: g(1) es una función que devuelve una función de una variable, g(1)(2) es otra función que devuelve una función de una variable, y finalmente g(1)(2)(3) es el resultado de computar el body de f.

Pasemos al otro contendiente.

Transformación por Aplicación Parcial

Esta vez iremos al grano. La transformada de f por aplicación parcial con primer argumento valiendo 7 es: 

h = partial1(7,f) = λ(y,z){body where x=7}
No os preocupéis en este momento de cómo es el operador partial1 ( que del operador curry no os habéis preocupado para nada ;-) Únicamente prestad atención a su resultado: es una función de dos variables que tiene "clausurado" en su environment el valor de x = 7.

Veamos la evaluación en este caso: 
f(7,2,3) = h(2,3)
También veremos con detalle este caso, que no va a ser menos que el otro :) 
h(2,3) =  λ(y,z){body where x=7} where y=2, z=3
       = body where x=7, y=2, z=3

Creo que no hay más que decir ... de momento.

El caso de dos variables

La fuente de las confusiones. Pero no nos adelantemos. Veamos que ocurre cuando tenemos 
f = λ(x,y){body}
Apliquemos la transformación de Curry y evaluemos el resultado en 7: 
g    = curry(f) = λ(x){ret λ(y){body}}

g(7) = λ(x){ret λ(y){body }} where x=7 
       λ(y){body where x=7}
Veamos ahora el resultado de la transformación aplicación parcial en 
h    = partial1(7,f) = 
     = λ(y){body where x=7}
Comparémoslos más cerca 
g(7) = curry(f)(7)   = λ(y){body where x=7} 
h    = partial1(7,f) = λ(y){body where x=7}
¡Son iguales! Para una función de dos variables la aplicación parcial en el primer argumento equivale a la evaluación de la transformada de Curry evaluada una vez.

Extrapolar sin control puede ser peligroso

Pero ¡ojo! que se cumpla para dos variables no significa que sea un equivalencia que se verifique para cualquier número variables así sin más condiciones. Vamos a aclarar lo que esta pasando. Supongamos que la función tiene n argumentos con n > 1
  1. La transformada de Curry es una función de una variable que devuelve otra función de una variable que ...(¿recordais el anuncion de Duracell?)
  2. La transformación Aplicación Parcial en una argumento es una función de n-1 argumentos
Es decir son diferentes. Pero algo las conecta:
Para una función de n variables la aplicación parcial en los primeros n-1 argumentos equivale a la evaluación n-1 veces de la transformada de Curry, obteniendose en ambos casos una función de una variable con el mismo cuerpo y enlaces variable-valor en el environment

¿Cómo son los operadores transformadores en el caso de los tres argumentos en JavaScript?

Vamos a empezar por los de la aplicación parcial primero, que son tres: 
partial1 = λ(x,f){ret λ(y,z){ret f(x,y,z)}}

partial2 = λ(y,f){ret λ(x,z){ret f(x,y,z)}}

partial3 = λ(z,f){ret λ(x,y){ret f(x,y,z)}}
Le toca el turno al "schöenfinkeling" 
curry = λ(f){ret λ(x){ret λ(y){ret λ(z){ret f(x,y,z)}}}}
¿Cómo?¿Qué eso no es JavaScript? Recordad la notación. Pero bueno, sea por el bien del corta-pega 
var partial1= function(x,f){
    return function(y,z){
         return f(x,y,z);
    };
}

...

var curry= function(f){
    return function(x){
         return function(y){
               return function(z){
                     return f(x,y,z);
               };
         };
    };
}
Seguramente la primera os sonará pero dudo que la segunda no creo.

¿Cómo sería la aplicación parcial de m argumentos en una función que tiene n parámetros formales?

Para una función de n parámetros formales existen n!/((n-m)!· m!) formas diferentes de aplicar argumentos. Supongo que os bastará con el caso en el que los argumentos aplicados son los m argumentos iniciales. 
var partial = function(f, arrayConLosArgumentosAplicados) {
  return function() {
     var argumentos = arrayConLosArgumentosAplicados.concat(arguments);//No funciona
     return f.apply(this,argumentos);
  };
}
¡Vaya!¿Qué es lo que ocurre? Lo que ocurre es que ¡arguments no es un array! Es un objeto muy interesante del que podemos hablar otro día. Ahora mismo lo que necesitamos saber es que se comporta como un objeto con una serie de propiedades con índices numéricos en secuencia, una propiedad length con la longitud de dicha secuencia, alguna que otra propiedad controvertida pero ni tiene los "métodos" de Array ni lo tiene como prototipo.

Por otra parte el "método" concat tiene un comportamiento diferente si el objeto a contatenar es un Array o no lo es. En este caso arguments no es un Array y en consecuencia no lo "aplanaría". Tendremos que preparar nuestra propia funciones para concatenar. No es complicado. 

var nuestroConcat  = function(primerObjetoConIndices,segundoObjetoConIndices) {
  var  array = [];
  var  i,len;     
  for (i = 0, len = primerObjetoConIndices.length; i < len; i++)
      array.push(primerObjetoConIndices[i]);
  for (i = 0, len = segundoObjetoConIndices.length; i < len; i++)
      array.push(segundoObjetoConIndices[i]);
  return array;
}

var partial = function(f, arrayConLosArgumentosAplicados) {
  return function() {
     var argumentos = nuestroConcat(arrayConLosArgumentosAplicados, arguments);
     return f.apply(this,argumentos);
  };
}

Esta versión si funciona. Es relativamente extensa pero funciona.

Puede ser que nos interese una variante en la que los argumentos aplicados no se pasen en un array, sino que se extiendan en una lista separada por comas convencional. Podríamos hacer esto: 


var nuestroConcat  = function(primerObjetoConIndices,segundoObjetoConIndices) {
  var  array = [];
  var  i,len;     
  for (i = 0, len = primerObjetoConIndices.length; i < len; i++) 
      array.push(primerObjetoConIndices[i]);
  for (i = 0, len = segundoObjetoConIndices.length; i < len; i++) 
      array.push(segundoObjetoConIndices[i]);
  return array;
}

//No funciona
var partial = function() {
  var f = arguments[0];
  var arrayConLosArgumentosAplicados = arguments.slice(1);//¡Aqui se rompe!
  return function() {
     var argumentos = nuestroConcat(arrayConLosArgumentosAplicados, arguments);
     return f.apply(this,argumentos);
  };
}

¡Vaya!¿Qué es lo que ocurre? Lo que ocurre es que como antes comentamos ¡arguments no es un array! y carece de "método" slice. No hay problema, nosotros preparamos uno: 

var nuestroSlice  = function(objetoConIndices,ini,fin) {
  var len = objetoConIndices.length;
  if (typeof fin === 'undefined') fin = len;
  else if (fin<0) fin = len-fin;
  var  array = [];   
  while (ini < fin) {
      array.push(objetoConIndices[ini]);
      ini++;
  }
  return array;
}

var nuestroConcat  = function(primerObjetoConIndices,segundoObjetoConIndices) {
  var  array = [];
  var  i,len;     
  for (i = 0, len = primerObjetoConIndices.length; i < len; i++)
      array.push(primerObjetoConIndices[i]);
  for (i = 0, len = segundoObjetoConIndices.length; i < len; i++) 
      array.push(segundoObjetoConIndices[i]);
  return array;
}


var partial = function() {
  var f = arguments[0];
  var arrayConLosArgumentosAplicados = nuestroSlice(arguments,1);
  return function() {
     var argumentos = nuestroConcat(arrayConLosArgumentosAplicados,arguments);
     return f.apply(this,argumentos);
  };
}

Está versión ya funciona.

Pero podríamos descubrir, leyendo la especificación de ECMAScript que el "método" slice de los Array no requiere que el objeto sobre el que se aplica sea un Array, simplemente necesita que sea un objeto con propiedades indices y la longitud de la secuencia. Podemos tomarlo prestado y aplicárselo a arguments 

Aquí podemos encontrar la función que nos interesa:

                       Array.prototype.slice

Forcémosla a creer que se esta aplicando indicando explicitamente el thisValue
mediante call:

                       Array.prototype.slice.call(arguments,1)
Ya no necesitamos nuestroSlice: 
var nuestroConcat  = function(primerObjetoConIndices,segundoObjetoConIndices) {
  var  array = [];
  var  i,len;     
  for (i = 0, len = primerObjetoConIndices.length; i < len; i++)
       array.push(primerObjetoConIndices[i]);
  for (i = 0, len = segundoObjetoConIndices.length; i < len; i++)
       array.push(segundoObjetoConIndices[i]);
  return array;
}


var partial = function() {
  var f = arguments[0];
  var arrayConLosArgumentosAplicados = Array.prototype.slice.call(arguments,1);
  return function() {
     var argumentos = nuestroConcat(arrayConLosArgumentosAplicados,arguments);
     return f.apply(this,argumentos);
  };
}
En estos momentos podemos darnos cuenta de otra cosa: si fabricamos una copia saneada de arguments que sea un auténtico Array podríamos utilizar concat sin problemas. ¿Y cómo podemos elaborar dicha copia? Fácil: nuestroSlice(arguments,0) o mejor aún Array.prototype.slice.call(arguments,0). Adios nuestroConcat. 
var partial = function() {
  var f = arguments[0];
  var arrayConLosArgumentosAplicados = Array.prototype.slice.call(arguments,1);
  return function() {
     var argumentos = 
              arrayConLosArgumentosAplicados.concat(Array.prototype.slice.call(arguments,0));
     return f.apply(this,argumentos);
  };
}
Nota: Por cierto, lo siento pero me niego a utilizar un objeto transitorio mediante literal [] en lugar de Array.prototype :)

Creo que es suficiente. La preparación de esta función para su inclusión en Function.prototype lo dejamos para otro día :)

¿Cómo sería la transformación de Curry para una función que tiene n parámetros formales?

Esto no está bajo el control de JavaScript ya que se necesitaría crear código nuevo dependiente del número de parámetros. Necesitamos macros y JavaScript no nos los proporciona.

Pero hay una solución: creemos el código fuente de la función y "compilémoslo" (ya me entendéis) 

var curry = function(f) {
  var n = f.length;
  var source =   '(';
  for (var j = 0; j< n; j++) source += 'function(p'+j+'){ return ';
  source += 'f(p0';
  for (  var j = 1; j< n; j++) source += ',p'+j;
  source += ');';
  for (  var j = 0; j< n; j++) source += '}';
  source += ');';
  return eval(source);
}
No es que quede muy bonito pero ya tenemos lo que queríamos :)

Conclusión

Resumiendo, conceptualmente la aplicación parcial y la transformación de Curry son totalmente diferentes. Si están relacionadas la aplicación parcial y la transformada de Curry evaluada hasta el penúltimo argumento.

La aplicación parcial es muy útil en JavaScript, y de hecho es lo que se usa implícitamente al utilizar Function.prototype.bind. Sobre la utilidad práctica de la transformación de Curry en JavaScript tengo serias dudas: viendo la implementación del transformador podemos apreciar que no parece "natural" en JavaScript.