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

Question

是否可以做 foldLeft在参数列表中，提供给折叠的初始值是一个完全柯里化(Currying)的函数，运算符是 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 的工作。 .

我第一次尝试描述 apply 的序列使用 foldLeft好像:

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 推导联合类型，所以如果第一个预感是真的，那么我似乎拥有解决问题所需的基 native 制。

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

T1 => ... => Tn

进入联合类型:

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

可用作 g 的类型多于。

做一个 foldLeft在 List将讨论限制在 T1 的情况。通过 Tn-1都是一样的。像这样的符号

(T1 =>)+ Tn

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

我要询问的具体情况不需要任意长的链，因此我们可以使用

(T1 =>){1,4} Tn

但是，展望想要对不相等的类型链执行此操作，也许一些将链切分成所有后缀集的类型的神奇功能更有用:

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

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

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

对我来说，命名这个问题并理解它相对于大局(类型理论、可判定性等)的位置比拥有 ANSWER 的工作实现更重要。 ，虽然两者都会很好。奖励点指向任何可以与 Scalaz、Monoids 或一般范畴理论建立联系的人。

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

我们也可以使用相同的未修改 foldCurry对于具有不同arity 和非统一参数类型的函数，

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)