Применение списка аргументов к функции карри с использованием foldLeft в Scala

Question

Можно ли сделать 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, поэтому, если это первое предположение верно, тогда у меня, похоже, есть основной механизм, необходимый для решения проблемы.

Однако: даже если типы объединенийОтвет был бы полезен, если бы я мог сослаться на «Объединение всех типов от полностью карризованного типа функции до типа каррированной функции со всеми, кроме последнего предоставленного аргумента».Другими словами, способ преобразования типа:

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, хотя оба были бы хороши.Бонусные очки начисляются всем, кто может подключиться к Скалазу, Моноидам или Теории категорий в целом.

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 для функций с различными типами аргументов арности и неоднородных

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.

Имея это в виду ( предупреждение очень un-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

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