Применение списка аргументов к curried-функции с помощью foldLeft в Scala

Можно ли сделать foldLeft в списке аргументов, где начальное значение, переданное в сгиб, является полностью картой, оператор 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) })

Моя первая мысль заключалась в том, что здесь будет полезен тип объединения. Я видел, как Майлз Сабин выводит типы профсоюзов с помощью Curry-Howard, поэтому, если эта первая догадка истинна, то у меня, похоже, есть основной механизм, необходимый для решения проблемы.

Однако: даже если типы объединения являются ответом, было бы полезно, если бы я мог ссылаться на "объединение всех типов из полностью карриного типа функции в тип функции 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 существующего типа или с помощью плагина компилятора или ни того, что я не знаю.

Как было отмечено в комментариях ниже, при вызове результата "тип объединения" не подходит для этого варианта использования. Я не знаю, что еще назвать, но это самая близкая идея, которую я имею в данный момент. У других языков есть особая поддержка этой идеи? Как это будет работать в Кок и Агда?

Именование этой проблемы и понимание того, где она сидит по отношению к большей картине (теории типов, разрешимости и т.д.), важнее для меня, чем выполнение рабочей реализации ANSWER, хотя оба они были бы хороши. Бонус указывает на всех, кто может подключаться к Scalaz, Monoids или Category Theory вообще.

Ответ 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 и non-uniform arguments,

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)

Ответ 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.

С учетом этого (предупреждение очень не-w60 > ):

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

Ответ 3

Хорошо, нет скаляза и никакого решения, кроме объяснения. Если вы используете ваш f.curried.apply с 1, а затем с 2 аргументами в REPL, наблюдайте, что типы возвращаемого результата DO действительно различаются каждый раз! FoldLeft довольно прост. Он зафиксировал в нем тип с вашим исходным аргументом, который является f.curried, и поскольку у него нет той же самой подписи, что и f.curried.apply(1), он не работает. Поэтому начальный аргумент и результат должны быть одного типа. Тип должен быть последовательным для элемента start-sum foldLeft. И ваш результат будет даже Int, так что это абсолютно не сработает. Надеюсь, это поможет.