在普通 Scala 3 中表达任意数量的函数

Question

尝试掌握 Scala 3 类型系统。问题：

• 是否可以编写一个def curry(f: ???) = ...接受f任意数量并返回柯里化 fn 的通用函数？没有编译器插件，没有外部花哨的库，只是用普通 Scala 3 表达的 N 元函数？
• 我看一下这个 Haskell 示例https://riptutorial.com/haskell/example/18470/an-n-arity-curry，它的功能类似于所需的功能。

（这个问题的目的不是使用任何外部库 - 目的是学习使用 Scala 3 作为工具的函数式编程概念。有一种感觉，这可能与将 args 作为元组处理或将 fn 转换为元组 fn 相关？我觉得 fn args 和元组的概念之间存在一些对称性？）

Answer 1

与 Haskell 相反，Scala 中有不同的函数类型(X1, ..., Xn) => Y（又名FunctionN[X1, ..., Xn, Y]）和((X1, ..., Xn)) => Y（又名Function1[TupleN[X1, ..., Xn], Y]）。对于后者（为了将它们转换为X1 => ... => Xn => Y又名Function1[X1, Function1[..., Function1[Xn, Y]...]]），您可以使用匹配类型、内联方法和编译时操作

import scala.compiletime.{erasedValue, summonFrom}

type Reverse[T <: Tuple] = ReverseLoop[T, EmptyTuple]

inline def reverse[T <: Tuple](t: T): Reverse[T] = reverseLoop(t, EmptyTuple)

type ReverseLoop[T <: Tuple, S <: Tuple] <: Tuple = T match
  case EmptyTuple => S
  case h *: t => ReverseLoop[t, h *: S]

inline def reverseLoop[T <: Tuple, S <: Tuple](x: T, acc: S): ReverseLoop[T, S] =
  inline x match
    case _: EmptyTuple => acc
    case x: (_ *: _) => x match
      case h *: t => reverseLoop(t, h *: acc)

type Curry[T <: Tuple, Y] = CurryLoop[T, T, EmptyTuple, Y]

inline def curry[T <: Tuple, Y](f: T => Y): Curry[T, Y] =
  curryLoop[T, T, EmptyTuple, Y](f, EmptyTuple)

type CurryLoop[T1 <: Tuple, T <: Tuple, S <: Tuple, Y] = T1 match
  case EmptyTuple => Y
  case h *: t => h => CurryLoop[t, T, h *: S, Y]

inline def curryLoop[T1 <: Tuple, T <: Tuple, S <: Tuple, Y](
  f: T => Y,
  acc: S
): CurryLoop[T1, T, S, Y] = inline erasedValue[T1] match
  case _: EmptyTuple => summonFrom {
    case _: (Reverse[S] =:= T) => f(reverse(acc))
  }
  case _: (h *: t) => (h: h) => curryLoop[t, T, h *: S, Y](f, h *: acc)

测试：

// compiles
summon[Curry[(Int, String, Boolean), String] =:= (Int => String => Boolean => String)]

val f: ((Int, String, Boolean)) => String = t => s"${t._1}, ${t._2}, ${t._3}"
val g = curry(f)
g: (Int => String => Boolean => String) // checking the type
g(1)("a")(true) // 1, a, true

Scala 3：类型化元组压缩

或者，您仍然可以使用好的旧类型类

trait Reverse[T <: Tuple]:
  type Out <: Tuple
  def apply(t: T): Out

object Reverse:
  type Aux[T <: Tuple, Out0 <: Tuple] = Reverse[T] {type Out = Out0}
  def instance[T <: Tuple, Out0 <: Tuple](f: T => Out0): Aux[T, Out0] =
    new Reverse[T]:
      override type Out = Out0
      override def apply(t: T): Out = f(t)

  given [T <: Tuple](using
    reverseLoop: ReverseLoop[T, EmptyTuple]
  ): Aux[T, reverseLoop.Out] = instance(t => reverseLoop(t, EmptyTuple))

trait ReverseLoop[T <: Tuple, S <: Tuple]:
  type Out <: Tuple
  def apply(t: T, acc: S): Out

object ReverseLoop:
  type Aux[T <: Tuple, S <: Tuple, Out0 <: Tuple] =
    ReverseLoop[T, S] {type Out = Out0}
  def instance[T <: Tuple, S <: Tuple, Out0 <: Tuple](
    f: (T, S) => Out0
  ): Aux[T, S, Out0] = new ReverseLoop[T, S]:
    override type Out = Out0
    override def apply(t: T, acc: S): Out = f(t, acc)

  given [S <: Tuple]: Aux[EmptyTuple, S, S] = instance((_, acc) => acc)

  given [H, T <: Tuple, S <: Tuple](using
    reverseLoop: ReverseLoop[T, H *: S]
  ): Aux[H *: T, S, reverseLoop.Out] =
    instance((l, acc) => reverseLoop(l.tail, l.head *: acc))

trait Curry[T <: Tuple, Y]:
  type Out
  def apply(f: T => Y): Out

object Curry:
  type Aux[T <: Tuple, Y, Out0] = Curry[T, Y] {type Out = Out0}
  def instance[T <: Tuple, Y, Out0](g: (T => Y) => Out0): Aux[T, Y, Out0] =
    new Curry[T, Y]:
      override type Out = Out0
      override def apply(f: T => Y): Out = g(f)

  given [T <: Tuple, Y](using
    curryLoop: CurryLoop[T, T, EmptyTuple, Y]
  ): Aux[T, Y, curryLoop.Out] = instance(f => curryLoop(f, EmptyTuple))

trait CurryLoop[T1 <: Tuple, T <: Tuple, S <: Tuple, Y]:
  type Out
  def apply(f: T => Y, acc: S): Out

object CurryLoop:
  type Aux[T1 <: Tuple, T <: Tuple, S <: Tuple, Y, Out0] =
    CurryLoop[T1, T, S, Y] {type Out = Out0}
  def instance[T1 <: Tuple, T <: Tuple, S <: Tuple, Y, Out0](
    g: (T => Y, S) => Out0
  ): Aux[T1, T, S, Y, Out0] = new CurryLoop[T1, T, S, Y]:
    override type Out = Out0
    override def apply(f: T => Y, acc: S): Out = g(f, acc)

  given [S <: Tuple, Y](using
    reverse: Reverse[S]
  ): Aux[EmptyTuple, reverse.Out, S, Y, Y] =
    instance((f, acc) => f(reverse(acc)))

  given [H1, T1 <: Tuple, T <: Tuple, S <: Tuple, Y](using
    curryLoop: CurryLoop[T1, T, H1 *: S, Y]
  ): Aux[H1 *: T1, T, S, Y, H1 => curryLoop.Out] =
    instance((f, acc) => h1 => curryLoop(f, h1 *: acc))

def curry[T <: Tuple, Y](f: T => Y)(using
  curryInst: Curry[T, Y]
): curryInst.Out = curryInst(f)

测试：

// compiles
summon[Curry.Aux[(Int, String, Boolean), String, Int => String => Boolean => String]]

val c = summon[Curry[(Int, String, Boolean), String]]  // compiles
summon[c.Out =:= (Int => String => Boolean => String)] // compiles

val f: ((Int, String, Boolean)) => String = t => s"${t._1}, ${t._2}, ${t._3}"
val g = curry(f)
g: (Int => String => Boolean => String) // checking the type
g(1)("a")(true) // 1, a, true

tupled转换(X1, ..., Xn) => Y为的方法可以作为透明宏((X1, ..., Xn)) => Y来实现。宏是透明的（这对应于Scala 2 中的白盒）意味着它可以返回比声明的类型更精确的类型。

import scala.quoted.*

transparent inline def tupled[F](f: F): Any = ${tupledImpl('f)}

def tupledImpl[F: Type](f: Expr[F])(using Quotes): Expr[Any] =
  import quotes.reflect.*

  val allTypeArgs = TypeRepr.of[F].typeArgs
  val argTypes    = allTypeArgs.init
  val argCount    = argTypes.length
  val returnType  = allTypeArgs.last

  val tupleType = AppliedType(
    TypeRepr.typeConstructorOf(Class.forName(s"scala.Tuple$argCount")),
    argTypes
  )

  (tupleType.asType, returnType.asType) match
    case ('[t], '[b]) => '{
      (a: t) => ${
        Apply(
          Select.unique(f.asTerm, "apply"),
          (1 to argCount).toList.map(i => Select.unique('a.asTerm, s"_$i"))
        ).asExprOf[b]
      }
    }

测试：

val f: (Int, String, Boolean) => String = (i, s, b) => s"$i, $s, $b"
val g = tupled(f)
g: (((Int, String, Boolean)) => String) // checking the type
g((1, "a", true)) // 1, a, true

这给了我们curry类型(X1, ..., Xn) => Y

curry(tupled(f))(1)("a")(true) // 1, a, true

尽管curry(tupled(f))适用于特定的方法，f但指定方法的签名并不容易（组合curry和tupled）

// for match-type implementation of curry

transparent inline def curry1[F](f: F): Any = curry(tupled(f))

curry1(f)(1)("a")(true)
// doesn't compile: method curry1 ... does not take more parameters

// for type-class implementation of curry

transparent inline def curry1[F](f: F): Any = curry(tupled(f))
// doesn't compile: No given instance of type Curry[Nothing, Any] was found...
// (and what types to specify in (using Curry[???, ???]) ?)

我认为如果我也制作宏，那么使用模式恢复精确类型应该会有所帮助curry1

transparent inline def curry1[F](f: F): Any = ${curry1Impl[F]('f)}

def curry1Impl[F: Type](f: Expr[F])(using Quotes): Expr[Any] =
  import quotes.reflect.*

  '{ tupled[F]($f) } match
    case
      '{
        type t <: Tuple
        $x: (`t` => y)
      } =>
        Expr.summon[Curry[t, y]] match
          case Some(c) => '{curry[t, y]($x)(using $c)}

但事实并非如此。如果transparent inline def tupled[F](f: F): Any = ...则不'{ tupled[F]($f) }匹配'{...; $x: (`t` => y)}。如果是transparent inline def tupled[F](f: F): Function1[?, ?] = ...的话，就是。tNothingyAny

因此，让我们制作tupled一个隐式宏（类型类），以便更好地控制返回类型tupled

import scala.quoted.*

trait Tupled[F]:
  type Out
  def apply(f: F): Out

object Tupled:
  type Aux[F, Out0] = Tupled[F] { type Out = Out0 }
  def instance[F, Out0](g: F => Out0): Aux[F, Out0] = new Tupled[F]:
    type Out = Out0
    def apply(f: F): Out = g(f)

  transparent inline given [F]: Tupled[F] = ${mkTupledImpl[F]}

  def mkTupledImpl[F: Type](using Quotes): Expr[Tupled[F]] =
    import quotes.reflect.*
    val allTypeArgs = TypeRepr.of[F].typeArgs
    val argTypes    = allTypeArgs.init
    val argCount    = argTypes.length
    val returnType  = allTypeArgs.last

    val tupleType = AppliedType(
      TypeRepr.typeConstructorOf(Class.forName(s"scala.Tuple$argCount")),
      argTypes
    )

    (tupleType.asType, returnType.asType) match
      case ('[t], '[b]) => '{
        instance[F, t => b]((f: F) => (a: t) => ${
          Apply(
            Select.unique('f.asTerm, "apply"),
            (1 to argCount).toList.map(i => Select.unique('a.asTerm, s"_$i"))
          ).asExprOf[b]
        })
      }

def tupled[F](f: F)(using tupledInst: Tupled[F]): tupledInst.Out = tupledInst(f)

// for match-type implementation of curry

inline def curry1[F, T <: Tuple, Y](f: F)(using
  tupledInst: Tupled[F],
  ev: tupledInst.Out <:< (T => Y),
): Curry[T, Y] = curry(tupled(f))

测试：

val f: (Int, String, Boolean) => String = (i, s, b) => s"$i, $s, $b"
val g = curry1(f)
g : (Int => String => Boolean => String) // checking the type
g(1)("a")(true) // 1, a, true

或者tupled，您可以尝试内置类型类scala.util.TupledFunction https://docs.scala-lang.org/scala3/reference/experimental/tupled-function.html（感谢@MartinHH 在评论中指出这一点）

// for match-type implementation of curry

inline def curry1[F, T <: Tuple, Y](f: F)(using
  tf: TupledFunction[F, T => Y]
): Curry[T, Y] = curry(tf.tupled(f))

// for type-class implementation of curry

def curry1[F, T <: Tuple, Y](f: F)(using
  tf: TupledFunction[F, T => Y],
  c: Curry[T, Y]
): c.Out = curry(tf.tupled(f))

TupledFunction类似于shapeless.ops.function.{FnToProduct, FnFromProduct}Scala 2 中的类型类

https://github.com/milessabin/shapeless/wiki/Feature-overview:-shapeless-2.0.0#facilities-for-abstracting-over-arity

Scala 中针对任意输入参数的偏函数应用

以任意数量的另一个函数作为参数的函数

Scala 的类型系统和 FunctionN 的输入