spark - Aplicación de una lista de argumentos a la función curried utilizando foldLeft en Scala

foldleft spark

Question

¿Es posible hacer una foldLeft en una lista de argumentos, donde el valor inicial proporcionado para el fold 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, digamos 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 de a uno por 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, parece un trabajo para foldLeft .

Mi primer intento de describir esta secuencia de apply utilizando foldLeft es similar a:

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 tipo necesitaría alguna pista para g .

La solución que estoy buscando 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) })

Lo primero que pensé fue que un tipo de unión sería útil aquí. 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 al currículum completo al tipo de la función curried con todo menos el último argumento proporcionado". En otras palabras, una forma 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 anterior.

Hacer una foldLeft en una List limita la discusión al caso donde T1 a Tn-1 son todos iguales. Una notación como

(T1 =>)+ Tn

describiría el tipo que quiero proporcionar para g .

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

(T1 =>){1,4} Tn

Sin embargo, si queremos hacer esto para cadenas de tipos que no son iguales, tal vez sea más útil alguna función mágica sobre los tipos que interrumpan la cadena en el conjunto de todos los sufijos:

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

Implementar esto está más allá de mis capacidades de 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 ubica con respecto a la perspectiva general (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 bastante más simple de lo que inicialmente esperaba.

Primero necesitamos definir una HList simple,

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 de plegado de forma inductiva con la ayuda de una clase de tipo,

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 usarlo así, 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 la misma foldCurry no modificada para funciones con tipos de foldCurry diferentes y argumentos 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 argumentos Int . foldLeft es una función que se aplica a una cantidad arbitraria de elementos. Usted menciona List(1,2,3,4) pero ¿qué List(1,2,3,4) si tiene List(1,2,3,4,5) o List() ?

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

Cualquier solución que se te ocurra tampoco sería general. Por ejemplo, ¿qué ocurre si tu función es de tipo (Int, Float, Int, String) => Int ? Entonces necesitarías una List[Any]

Definitivamente no es un trabajo para List.foldLeft .

Con eso en mente ( advertencia muy poco código 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