在 Scala 中使用 foldLeft 将参数列表应用于咖喱函数 [英] Applying an argument list to curried function using foldLeft in Scala

问题描述

是否可以对参数列表执行 foldLeft，其中提供给折叠的初始值是一个完全柯里化的函数，运算符是 apply，并且该列表是要传递给函数 f?

Is it possible to do a foldLeft on a list of arguments, where the initial value supplied to the fold is a fully curried function, the operator is apply, and the list is a list of arguments to be passed to function f?

例如，假设 f 定义为:

For example, let's say f is defined as:

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

我们当然可以直接使用:

Which we can of course use directly:

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

或者咖喱并一次应用一个参数:

Or curry and apply the arguments one at a time:

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 的工作.

At first glance this looks like a job for foldLeft.

我第一次尝试使用 foldLeft 描述这个 apply 序列看起来像:

My first attempt at describing this sequence of apply using foldLeft looks like:

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

然而，这会产生以下错误:

However, that yields the following error:

<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 进行一些提示.

My reading of the error message is that type inference would need some hint for g.

我正在寻找的解决方案在我的原始表达式中除了 g 的类型之外的所有内容都没有修改:

The solution I'm looking for leaves everything unmodified in my original expression except the type of g:

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

我的第一个想法是联合类型在这里会很有用.我已经看到 Miles Sabin 使用 Curry-Howard 推导出联合类型，所以如果第一个预感是真的，那么我似乎拥有解决问题所需的基本机制.

My first thought was that a union type would be useful here. I've seen Miles Sabin's derivation of union types using Curry-Howard, so if that first hunch is true, then I appear to have the basic machinery required to solve the problem.

然而:即使联合类型是答案，如果我可以参考从函数的完全柯里化类型到柯里化函数的类型的所有类型的联合，除了最后一个参数之外的所有类型".换句话说，一种转换类型的方法:

However: Even if union types are the answer it would be useful if I could refer to "The union of all types from the fully curried type of a function to the type of the curried function with all but the last argument supplied". In other words, a way to turn the type:

T1 => ... => Tn

进入联合类型:

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

作为上述 g 的类型很有用.

would be useful as the type for g above.

在 List 上执行 foldLeft 将讨论限制为 T1 到 Tn-1 都是相同.像

Doing a foldLeft on a List limits the discussion to case where T1 through Tn-1 are all the same. A notation like

(T1 =>)+ Tn

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

would describe the type I want to provide for g.

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

The specific case I'm asking about doesn't require arbitrarily long chains, so we could provide bounds on the iterator using

(T1 =>){1,4} Tn

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

Looking ahead at wanting to do this for chains of types that are not equal, though, perhaps some magical function on types that chops up the chain into the set of all suffixes is more useful:

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

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

Implementing this is well beyond my Scala abilities at the moment. Any hints as to how to go about doing so would be appreciated. Whether this can be done with advanced usage of Scala's existing type system or through a compiler plugin or neither, I do not know.

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

As has been noted in the comments below, calling the result a "union type" is not a perfect fit for this use case. I don't know what else to call it, but that's the closest idea I have at the moment. Do other languages have special support for this idea? How would this work in Coq and Agda?

命名这个问题并理解它相对于更大的图景(类型理论、可判定性等)的位置对我来说比拥有 ANSWER 的有效实现更重要，尽管两者都是会好的.任何能够与 Scalaz、Monoids 或范畴论建立联系的人都会得到奖励.

Naming this problem and understanding where it sits with respect to the bigger picture (of type theory, decidability, and so forth) is more important to me than having a working implementation of ANSWER, though both would be nice. Bonus points to anyone who can draw connections to Scalaz, Monoids, or Category Theory in general.

推荐答案

事实证明这比我最初预期的要简单得多.

This turns out to be quite a bit simpler than I initially expected.

首先我们需要定义一个简单的HList，

First we need to define a simple 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]

然后我们可以借助类型类归纳地定义我们的折叠函数，

Then we can define our fold-like function inductively with the aid of a type class,

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)

我们可以这样使用它，首先用于您的原始示例，

We can use it like this, first for your original example,

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，

And we can also use the same unmodified foldCurry for functions with different arity's and non-uniform argument types,

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)

这篇关于在 Scala 中使用 foldLeft 将参数列表应用于咖喱函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！