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

Question

是否可以foldLeft在参数列表上执行a ,其中提供给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.

我第一次尝试描述这个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推导联合类型,所以如果第一次预感是真的,那么我似乎拥有解决问题所需的基本机制.

但是:即使联合类型是答案,如果我可以引用"从完全curried类型的函数到curried函数的类型的所有类型的并集,除了提供的最后一个参数之外",它将是有用的.换句话说,一种转变类型的方法:

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)

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