scala:无论函数有多少参数，都要记住一个函数？

Question

我想在 scala 中编写一个 memoize 函数，该函数可以应用于任何函数对象，无论该函数对象是什么。我想以一种允许我使用 memoize 的单一实现的方式这样做。我对语法很灵活，但理想情况下，memoize 出现在非常接近函数声明的地方，而不是在函数之后。我还想避免先声明原始函数，然后再声明内存版本。

所以一些理想的语法可能是这样的:

def slowFunction(<some args left intentionally vague>) = memoize {
  // the original implementation of slow function
}

甚至这是可以接受的:

def slowFUnction = memoize { <some args left intentionally vague> => {
  // the original implementation of slow function
}}

我已经看到了必须为每个 arity 函数重新定义 memoize 的方法，但我想避免这种方法。原因是我需要实现几十个类似于 memoize 的函数(即其他装饰器)，并且要求为每个 arity 函数复制每个函数太过分了。

一种需要你重复 memoize 声明的 memoize 方法(所以它不好)是在 What type to use to store an in-memory mutable data table in Scala? .

Answer 1

您可以使用类型类方法来处理 arity 问题。您仍然需要处理要支持的每个函数 arity，但不是针对每个 arity/decorator 组合:

/**
 * A type class that can tuple and untuple function types.
 * @param [U] an untupled function type
 * @param [T] a tupled function type
 */
sealed class Tupler[U, T](val tupled: U => T, 
                          val untupled: T => U)

object Tupler {
   implicit def function0[R]: Tupler[() => R, Unit => R] =
      new Tupler((f: () => R) => (_: Unit) => f(),
                 (f: Unit => R) => () => f(()))
   implicit def function1[T, R]: Tupler[T => R, T => R] = 
      new Tupler(identity, identity)
   implicit def function2[T1, T2, R]: Tupler[(T1, T2) => R, ((T1, T2)) => R] = 
      new Tupler(_.tupled, Function.untupled[T1, T2, R]) 
   // ... more tuplers
}

然后，您可以按如下方式实现装饰器:

/**
 * A memoized unary function.
 *
 * @param f A unary function to memoize
 * @param [T] the argument type
 * @param [R] the return type
 */
class Memoize1[-T, +R](f: T => R) extends (T => R) {
   // memoization implementation
}

object Memoize {
   /**
    * Memoize a function.
    *
    * @param f the function to memoize
    */
   def memoize[T, R, F](f: F)(implicit e: Tupler[F, T => R]): F = 
      e.untupled(new Memoize1(e.tupled(f)))
}

您的“理想”语法将不起作用，因为编译器会假定 block 传递到 memoize是一个 0 参数的词法闭包。但是，您可以使用后一种语法:

// edit: this was originally (and incorrectly) a def
lazy val slowFn = memoize { (n: Int) => 
   // compute the prime decomposition of n
}

编辑:

为了消除定义新装饰器的大量样板，您可以创建一个特征:

trait FunctionDecorator {
   final def apply[T, R, F](f: F)(implicit e: Tupler[F, T => R]): F = 
      e.untupled(decorate(e.tupled(f)))

   protected def decorate[T, R](f: T => R): T => R
}

这允许您将 Memoize 装饰器重新定义为

object Memoize extends FunctionDecorator {
   /**
    * Memoize a function.
    *
    * @param f the function to memoize
    */
   protected def decorate[T, R](f: T => R) = new Memoize1(f)
}

而不是调用 memoize在 Memoize 对象上的方法，您直接应用 Memoize 对象:

// edit: this was originally (and incorrectly) a def
lazy val slowFn = Memoize(primeDecomposition _)

或者

lazy val slowFn = Memoize { (n: Int) =>
   // compute the prime decomposition of n
}