scala:无论函数有多少个参数都记住一个函数? [英] scala: memoize a function no matter how many arguments the function takes?

问题描述

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

i want to write a memoize function in scala that can be applied to any function object no matter what that function object is. i want to do so in a way that lets me use a single implementation of memoize. i'm flexible about the syntax, but ideally the memoize appears somewhere very close to the declaration of the function as opposed to after the function. i'd also like to avoid first declaring the original function and then a second declaration for the memoized version.

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

so some ideal syntax might be this:

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

甚至这也是可以接受的:

or even this would be acceptable:

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

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

i've seen ways to do this where memoize must be redefined for each arity function, but i want to avoid this approach. the reason is that i will need to implement dozens of functions similar to memoize (i.e. other decorators) and it's too much to ask to have to copy each one for each arity function.

一种需要您重复 memoize 声明(因此没有好处)的 memoize 方法是 在 Scala 中使用什么类型来存储内存中的可变数据表?.

one way to do memoize that does require you to repeat memoize declarations (so it's no good) is at What type to use to store an in-memory mutable data table in Scala?.

推荐答案

您可以使用类型类方法来处理数量问题.您仍然需要处理您想要支持的每个函数参数，但不是每个参数/装饰器组合:

You can use a type-class approach to deal with the arity issue. You will still need to deal with each function arity you want to support, but not for every arity/decorator combination:

/**
 * 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
}

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

You can then implement the decorator as follows:

/**
 * 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 参数词法闭包.但是，您可以使用后一种语法:

Your "ideal" syntax won't work because the compiler would assume that the block passed into memoize is a 0-argument lexical closure. You can, however, use your latter syntax:

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

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

To eliminate a lot of the boilerplate for defining new decorators, you can create a trait:

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 装饰器重新定义为

This allows you to redefine the Memoize decorator as

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 对象:

Rather than invoking a memoize method on the Memoize object, you apply the Memoize object directly:

// 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
}

这篇关于scala:无论函数有多少个参数都记住一个函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！