在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