在Scala中使用foldLeft将参数列表应用于curried函数

Question

是否可以对参数列表执行foldLeft，其中提供给fold的初始值是一个完全fully函数，运算符是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

或者使用curry，一次应用一个参数：

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

我的第一个想法是，联合类型在这里会很有用。我看过Miles Sabin使用Curry-Howard派生的联合类型，所以如果第一个预感是正确的，那么我似乎拥有解决问题所需的基本机制。

然而:即使联合类型是答案，如果我可以引用“从函数的完全fully类型到除了最后一个参数之外的所有类型的fully函数类型的所有类型的联合”，这将是有用的。换句话说，一种转换类型的方法：

T1 => ... => Tn

转换为联合类型：

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

作为上面g的类型会很有用。

在List上执行foldLeft将讨论限制在T1到Tn-1都相同的情况。一种符号，如

(T1 =>)+ Tn

将描述我想要为g提供的类型。

我询问的特定情况不需要任意长的链，因此我们可以使用以下命令提供迭代器的界限

(T1 =>){1,4} Tn

但是，展望未来，对于不相等的类型链，可能会有一些神奇的类型函数将链分解为所有后缀的集合：

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

目前，实现这一点远远超出了我的Scala能力。任何关于如何做到这一点的提示都将不胜感激。这是否可以通过Scala现有类型系统的高级用法或通过编译器插件来实现，或者两者都不能实现，我不知道。

正如在下面的注释中所指出的，将结果称为“联合类型”并不完全适合这个用例。我不知道还能叫什么，但这是我目前最接近的想法。其他语言对这个想法有特殊的支持吗？这在Coq和Agda中是如何工作的？

对我来说，命名这个问题并从更大的角度理解它所处的位置(类型理论、可判断性等等)比拥有一个有效的ANSWER实现更重要，尽管两者都很好。奖金指向任何可以与Scalaz、Monoid或Category理论建立联系的人。

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

我们还可以对具有不同arity和非统一参数类型的函数使用相同的未经修改的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

您的函数需要恰好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

Answer 3

好吧，没有scalaz，也没有解决方案，而是一个解释。如果您的f.curried.apply使用1，然后在REPL中使用2个参数，请注意每次返回的结果类型确实不同！FoldLeft非常简单。它固定在它的类型中，你的起始参数是f.curried，因为它没有和f.curried.apply(1)相同的签名，所以它不起作用。所以起始参数和结果必须是相同类型的。对于foldLeft的起始和元素，类型必须一致。你的结果甚至会是Int，所以这绝对不会起作用。希望这能有所帮助。