scala:memoize函数,无论函数有多少参数？

Question

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

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

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声明(所以它没有用)是什么类型用于在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)))
}

你的"理想"语法不起作用,因为编译器会认为传入的块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
}