Aplicar una lista de argumentos a la función curried utilizando foldLeft en Scala

Question

¿Es posible hacer un foldLeft en una lista de argumentos, donde el valor inicial proporcionado para el plegado es una función completamente curried, el operador es apply y la lista es una lista de argumentos para pasar a la función f?

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> 

cual podemos, por supuesto, utilizar directamente:

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

o el curry y aplicar 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 

A primera vista, esto parece un trabajo para foldLeft.

Mi primer intento de describir esta secuencia de apply usando foldLeft parece:

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

Sin embargo, que produce el error siguiente:

<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 para g.

La solución Busco deja todo sin modificar en mi expresión original, excepto el tipo de g:

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 en este caso. He visto la derivación de sindicatos de Miles Sabin usando Curry-Howard, así que si esa primera corazonada es cierta, entonces parece que tengo la maquinaria básica requerida para resolver el problema.

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 del tipo de función completamente currificado al tipo de la función curried con todo menos el último argumento proporcionado ". En otras palabras, una manera de convertir el tipo:

T1 => ... => Tn 

en el tipo de unión:

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

sería útil como el tipo de g anteriormente.

Haciendo un foldLeft en un List limita la discusión a través de caso en T1Tn-1 son todos iguales. Una notación como

(T1 =>)+ Tn 

describiría el tipo que quiero prever g.

El caso específico que estoy preguntando por no requiere cadenas de longitud arbitraria, por lo que podríamos proporcionar los límites en el iterador utilizando

(T1 =>){1,4} Tn 

De cara a querer hacer esto para las cadenas de tipos que no están igualdad de condiciones, sin embargo, tal vez alguna función mágica sobre los tipos que las chuletas de la cadena en el conjunto de todos los sufijos es más útil:

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

la implementación de este es mucho más allá de mis capacidades Scala en este momento. Cualquier sugerencia sobre cómo hacerlo será apreciada. Si esto se puede hacer con un uso avanzado del sistema de tipos existente de Scala o mediante un plugin de compilación o ninguno, no lo sé.

Como se ha señalado en los comentarios a continuación, llamar al resultado "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 un apoyo especial para esta idea? ¿Cómo funcionaría esto en Coq y Agda?

Nombrar este problema y entender dónde se encuentra con respecto a la imagen más grande (de la teoría de tipos, decidability, etc.) es más importante para mí que tener una implementación operativa de ANSWER, aunque ambas serían buenas. Puntos de bonificación para cualquier persona que pueda establecer conexiones con Scalaz, Monoids o la teoría de categorías en general.

Answer 1

Esto resulta ser un poco más sencillo de lo que inicialmente esperaba.

Primero necesitamos definir un simple HList,

sealed trait HList 

final case class HCons[H, T <: HList](head : H, tail : T) extends HList { 
    def ::[H1](h : H1) = HCons(h, this) 
    override def toString = head+" :: "+tail.toString 
} 

trait HNil extends HList { 
    def ::[H1](h : H1) = HCons(h, this) 
    override def toString = "HNil" 
} 

case object HNil extends HNil 
type ::[H, T <: HList] = HCons[H, T] 

Entonces podemos definir nuestra función veces como inductivamente con la ayuda de un tipo de clase,

trait FoldCurry[L <: HList, F, Out] { 
    def apply(l : L, f : F) : Out 
} 

// Base case for HLists of length one 
implicit def foldCurry1[H, Out] = new FoldCurry[H :: HNil, H => Out, Out] { 
    def apply(l : H :: HNil, f : H => Out) = f(l.head) 
} 

// Case for HLists of length n+1 
implicit def foldCurry2[H, T <: HList, FT, Out] 
    (implicit fct : FoldCurry[T, FT, Out]) = new FoldCurry[H :: T, H => FT, Out] { 
    def apply(l : H :: T, f : H => FT) = fct(l.tail, f(l.head)) 
} 

// Public interface ... implemented in terms of type class and instances above 
def foldCurry[L <: HList, F, Out](l : L, f : F) 
    (implicit fc : FoldCurry[L, F, Out]) : Out = fc(l, f) 

Podemos utilizarlo como esto, primero para su ejemplo original,

val f1 = (i : Int, j : Int, k : Int, l : Int) => i+j+k+l 
val f1c = f1.curried 

val l1 = 1 :: 2 :: 3 :: 4 :: HNil 

// In the REPL ... note the inferred result type 
scala> foldCurry(l1, f1c) 
res0: Int = 10 

Y también podemos usar t él mismo sin modificar foldCurry para funciones diferentes con aridad de tipos de argumentos y no uniformes,

val f2 = (i : Int, s : String, d : Double) => (i+1, s.length, d*2) 
val f2c = f2.curried 

val l2 = 23 :: "foo" :: 2.0 :: HNil 

// In the REPL ... again, note the inferred result type 
scala> foldCurry(l2, f2c) 
res1: (Int, Int, Double) = (24,3,4.0) 

Answer 2

Ok no scalaz y no hay solución, pero una explicación. Si utiliza su f.curried.apply con 1 y luego con 2 argumentos en el REPL, observe que los tipos de resultados de retorno realmente difieren cada vez. FoldLeft es bastante simple. Está fijo en su tipo con su argumento de inicio que está f.curried y dado que no tiene la misma firma que f.curried.apply (1) no funciona. Entonces, el argumento inicial y el resultado TIENEN que ser del mismo tipo. El tipo debe ser consistente para el elemento de suma inicial de foldLeft. Y su resultado sería incluso Int, por lo que no funcionaría. Espero que esto ayude.

Answer 3

Su función espera exactamente 4 Int argumentos. foldLeft es una función que se aplica a una cantidad arbitraria de elementos. Usted menciona List(1,2,3,4), pero ¿qué pasa si tiene List(1,2,3,4,5) o List()?

List.foldLeft[B] espera también una función para devolver el mismo tipo B, pero en su caso Int y algunos Function1[Int, _] no es del mismo tipo.

Cualquier solución que se presente no sería general tampoco. Por ejemplo, ¿qué pasa si su función es del tipo (Int, Float, Int, String) => Int? Necesitaría entonces un List[Any]

Así que definitivamente es no un trabajo para List.foldLeft.

Con esto en mente (advertencia de código muy poco Scala):

class Acc[T](f: Function1[T, _]) { 
    private[this] var ff: Any = f 
    def apply(t: T): this.type = { 
    ff = ff.asInstanceOf[Function1[T,_]](t) 
    this 
    } 
    def get = ff match { 
    case _: Function1[_,_] => sys.error("not enough arguments") 
    case res => res.asInstanceOf[T] 
    } 
} 

List(1,2,3,4).foldLeft(new Acc(f.curried))((acc, i) => acc(i)).get 
// res10: Int = 10