Applicazione di un elenco di argomenti alla funzione di piegatura utilizzando foldLeft in Scala

Question

È possibile eseguire un foldLeft in un elenco di argomenti, in cui il valore iniziale fornito alla piega è una funzione completamente elaborata, l'operatore è apply e l'elenco è un elenco di argomenti da passare alla funzione f?

Per esempio, diciamo che f è definito come:

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

cui possiamo naturalmente utilizzare direttamente:

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

O curry e applicare gli argomenti uno alla volta:

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 prima vista sembra un lavoro per foldLeft.

Il mio primo tentativo di descrivere questa sequenza di apply usando foldLeft assomiglia:

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

tuttavia, che produce il seguente errore:

<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) }) 

La mia lettura del messaggio di errore è che l'inferenza dei tipi avrebbe bisogno di qualche suggerimento per g.

La soluzione che sto cercando lascia tutto non modificato nella mia espressione originale, tranne il tipo di g:

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

Il mio primo pensiero è stato che un tipo di unione sarebbe utile qui. Ho visto la derivazione di Miles Sabin dei tipi di unione usando Curry-Howard, quindi se quella prima impressione è vera, allora mi sembra di avere i meccanismi di base necessari per risolvere il problema.

Tuttavia: anche se i tipi di unione sono la risposta, sarebbe utile se potessi fare riferimento a "L'unione di tutti i tipi dal tipo completamente curried di una funzione al tipo di funzione al curry con tutto tranne l'ultimo argomento fornito ". In altre parole, un modo per trasformare il tipo:

T1 => ... => Tn 

nel tipo unione:

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

sarebbe utile come il tipo per g sopra.

Facendo un foldLeft su una List limita la discussione al caso in cui T1 attraverso Tn-1 sono tutti uguali. Una notazione come

(T1 =>)+ Tn 

sarebbe descrivere il tipo che voglio prevedere g.

Il caso specifico che sto chiedendo non richiede arbitrariamente lunghe catene, così abbiamo potuto fornire limiti sul iteratore utilizzando

(T1 =>){1,4} Tn 

Guardando avanti a voler fare questo per catene di tipi che non sono uguale, anche se, forse qualche funzione magica sui tipi che sminuzza la catena nel set di tutti i suffissi è più utile:

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

implementazione di questo è ben al di là delle mie capacità Scala al momento. Sarebbe apprezzato qualsiasi suggerimento su come farlo. Se questo può essere fatto con l'uso avanzato del sistema di tipi esistente di Scala o attraverso un plug-in del compilatore o nessuno dei due, non lo so.

Come è stato notato nei commenti seguenti, chiamare il risultato un "tipo di unione" non è perfetto per questo caso d'uso. Non so cos'altro dire, ma questa è l'idea più vicina che ho al momento. Altre lingue hanno un supporto speciale per questa idea? Come funzionerebbe in Coq e Agda?

La denominazione di questo problema e la comprensione di dove si colloca rispetto all'immagine più grande (di teoria dei tipi, decidibilità e così via) è più importante per me che avere un'implementazione funzionante di ANSWER, anche se entrambi sarebbero belli. Punti bonus per chiunque sia in grado di tracciare connessioni con Scalaz, Monoidi o Teoria delle categorie in generale.

Answer 1

Questo risulta essere un po 'più semplice di quanto mi aspettassi inizialmente.

In primo luogo abbiamo bisogno di definire un semplice 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] 

Poi possiamo definire la nostra funzione di piegatura simile induttivamente con l'aiuto di una classe 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) 

Possiamo utilizzarlo come questo, prima per il tuo esempio originale,

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 

E possiamo anche usare t egli stesso non modificato foldCurry per le funzioni con diversi arity e di tipi di argomenti non uniformi,

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 nessuno scalaz e nessuna soluzione ma una spiegazione. Se si usa f.curried.apply con 1 e poi con 2 argomenti nel REPL, si osservano i tipi di risultato restituiti DO in realtà differiscono ogni volta! FoldLeft è abbastanza semplice. È fisso nel suo tipo con il tuo argomento di partenza che è f.curried e dal momento che non ha la stessa firma di f.curried.apply (1) non funziona. Quindi l'argomento di partenza e il risultato devono essere dello stesso tipo. Il tipo deve essere coerente per l'elemento di somma iniziale di foldLeft. E il tuo risultato sarebbe pari a Int in modo che non funzionasse assolutamente. Spero che questo ti aiuti.

Answer 3

La vostra funzione prevede esattamente 4 argomenti Int. foldLeft è una funzione che si applica a un numero arbitrario di elementi. Hai menzionato List(1,2,3,4) ma cosa succede se hai List(1,2,3,4,5) o List()?

List.foldLeft[B] si aspetta anche una funzione per restituire lo stesso tipo B, ma nel tuo caso Int e alcuni Function1[Int, _] non è dello stesso tipo.

Qualsiasi soluzione tu sia, non sarebbe nemmeno generale. Ad esempio, cosa succede se la tua funzione è di tipo (Int, Float, Int, String) => Int? Avresti quindi bisogno di un List[Any]

Quindi è sicuramente non un lavoro per List.foldLeft.

Con questo in mente (avvertimento codice molto 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