Aplicando una lista de argumentos a la función curry usando foldLeft en Scala

Question

Sep 30, 2011, 08:14 AM

Aplicando una lista de argumentos a la función curry usando foldLeft en Scala

¿Es posible hacer unfoldLeft en una lista de argumentos, donde el valor inicial suministrado al pliegue es una función completamente currificada, el operador esapply, y la lista es una lista de argumentos para pasar a la funciónf?

Por ejemplo, supongamos que f se define como:

scala> val f = (i: Int, j: Int, k: Int, l: Int) => i+j+k+l
f: (Int, Int, Int, Int) => Int = <function4>

Que, por supuesto, podemos usar directamente:

scala> f(1, 2, 3, 4)
res1: Int = 10

O curry y aplique los argumentos uno a la vez:

scala> f.curried
res2: Int => Int => Int => Int => Int = <function1>

scala> f.curried.apply(1).apply(2).apply(3).apply(4)
res3: Int = 10

primera vista, esto parece un trabajo parafoldLeft.

Mi primer intento de describir esta secuencia deapply utilizandofoldLeft parece

scala> List(1, 2, 3, 4).foldLeft(f.curried)({ (g, x) => g.apply(x) })

Sin embargo, eso produce el siguiente error:

<console>:9: error: type mismatch;
 found   : Int => Int => Int => Int
 required: Int => Int => Int => Int => Int
              List(1, 2, 3, 4).foldLeft(f.curried)({ (g, x) => g.apply(x) })

Mi lectura del mensaje de error es que la inferencia de tipos necesitaría alguna pista parag.

a solución que busco deja todo sin modificar en mi expresión original, excepto el tipo deg:

List(1, 2, 3, 4).foldLeft(f.curried)({ (g: ANSWER, x) => g.apply(x) })

Mi primer pensamiento fue que un tipo de unión sería útil aquí. He visto la derivación de tipos de unión de Miles Sabin usando Curry-Howard, así que si esa primera corazonada es cierta, entonces parece que tengo la maquinaria básica necesaria para resolver el problem

Sin embargo: incluso si los tipos de unión son la respuesta, sería útil si pudiera referirme a "La unión de todos los tipos, desde el tipo completamente currificado de una función hasta el tipo de función currificada con todos menos el último argumento suministrado". En otras palabras, una forma de cambiar el tipo:

T1 => ... => Tn

en el tipo de unión:

(T1 => ... => Tn) |∨| ... |∨| (Tn-1 => Tn)

sería útil como tipo parag encima

Hacer unfoldLeft en unList limita la discusión al caso dondeT1 medianteTn-1 son todos iguales. Una notación como

(T1 =>)+ Tn

describiría el tipo que quiero proporcionar parag.

El caso específico que estoy preguntando no requiere cadenas arbitrariamente largas, por lo que podríamos proporcionar límites en el iterador usando

(T1 =>){1,4} Tn

Mirando hacia adelante para querer hacer esto para cadenas de tipos que no son iguales, sin embargo, tal vez sea más útil alguna función mágica en tipos que dividen la cadena en el conjunto de todos los sufijos:

Suffixes(T1 => ... => Tn)

Implementar esto está más allá de mis habilidades Scala en este momento. Cualquier sugerencia sobre cómo hacerlo sería apreciada. Si esto se puede hacer con el uso avanzado del sistema de tipos existente de Scala o mediante un complemento de compilación o ninguno de los dos, no lo sé.

Como se ha señalado en los comentarios a continuación, llamar al resultado un "tipo de unión" no es perfecto para este caso de uso. No sé cómo llamarlo, pero esa es la idea más cercana que tengo en este momento. ¿Otros idiomas tienen soporte especial para esta idea? ¿Cómo funcionaría esto en Coq y Agda?

Nombrar este problema y comprender dónde se ubica con respecto a la imagen más grande (de la teoría de tipos, la capacidad de decisión, etc.) es más importante para mí que tener una implementación funcional deANSWER, aunque ambos estarían bien. Los puntos de bonificación apuntan a cualquiera que pueda establecer conexiones con Scalaz, los monoides o la teoría de categorías en general.

Deja tu comentario