在Scala中使用foldLeft對curried函數應用參數列表

Question

是否可以在參數列表上執行foldLeft，其中提供給fold的初始值是完全curried函數，運算符是apply，列表是要傳遞給函數f的參數列表？

例如，假設f定義爲：

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

對此我們當然可以直接使用：

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

或者咖喱和應用的參數每次一個：

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

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

乍一看，這看起來像一個foldLeft的工作。

我在使用foldLeft描述的apply此序列第一次嘗試看起來像：

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

然而，產生以下錯誤：

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

我的錯誤消息的讀數是類型推斷將需要一些暗示g。

我在尋找解決辦法離開我的一切原始表達式未修改除外g類型：

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

我首先想到的是，一個聯合類型在這裏很有用。我已經看到了邁克爾薩賓用庫裏霍華德推導出的聯盟類型，所以如果第一次預感是真的，那麼我似乎有解決問題所需的基本機制。

但是：即使union類型是答案，如果我可以引用「從完全curried類型的函數到curried函數類型的所有類型的聯合，並提供除最後一個參數以外的所有類型」。換句話說，一個辦法把類型：

T1 => ... => Tn 

到聯合類型：

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

將是作爲用於上述g類型是有用的。

否則在ListfoldLeft一個限制的討論情況下T1通過Tn-1都是相同的。類似

(T1 =>)+ Tn 

將描述我想爲g提供的類型。

我問不需要任意長鏈的具體情況，所以我們可以使用

(T1 =>){1,4} Tn 

在想對於不是類型鏈做到這一點展望未來提供的迭代器範圍平等的，但是，也許在某些類型的神奇功能是砍下了鏈到集合中的所有後綴是比較有用的：

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

實現這個遠遠超出目前我的斯卡拉能力。值得讚賞的是如何去做這些事情的提示。這是否可以通過Scala的現有類型系統的高級用法或通過編譯器插件來完成，或者我都不知道。

如以下注釋中所述，將結果稱爲「聯合類型」不適合此用例。我不知道還有什麼可以稱之爲的，但這是我目前最接近的想法。其他語言對這個想法有特別的支持嗎？這將如何在Coq和Agda工作？

對於我來說，命名這個問題並理解它的位置（類型理論，可判定性等等）對於我來說比對ANSWER的工作實現更重要，儘管兩者都很好。獎金指向任何可以與Scalaz，Monoid或類別理論相關聯的人。

Answer 1

這原來是簡單的，比我最初的預期不少。

首先，我們需要定義一個簡單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] 

然後，我們可以用一個類型類的輔助感應定義我們的褶皺之類的函數，

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) 

我們可以使用它像這個，首先爲你原來的例子，

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 

而且我們也可以用t他同樣未修改foldCurry與不同的元數的和非均勻的參數類型的函數，

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

好吧沒有scalaz和解決方案，但沒有解釋。如果你在1中使用f.curried.apply，然後在REPL中使用2個參數，則觀察返回結果類型DO實際上每次都不相同！ FoldLeft非常簡單。它的類型是固定的，它的起始參數是f.curried，因爲它和f.curried.apply（1）的簽名不一樣。 所以起始參數和結果必須是相同的類型。類型hast與foldLeft的starting-sum元素保持一致。而且你的結果甚至是Int，所以絕對不行。希望這可以幫助。

Answer 3

您的函數需要正好4 Int參數。 foldLeft是適用於任意數量元素的函數。你提到List(1,2,3,4)但如果你有List(1,2,3,4,5)或List()？

List.foldLeft[B]也期望一個函數返回相同的類型B，但在你的情況下Int和一些Function1[Int, _]是不是相同的類型。

無論你想出什麼解決方案都不是一般的。例如，如果你的功能是(Int, Float, Int, String) => Int？你需要一個List[Any]

所以它絕對是不是List.foldLeft的工作。

考慮到這一點（警示非常不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