我想用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
}}
我见过这样做的方法,必须为每个函数重新定义memoize,但我想避免这种方法。原因是我将需要实现几十个类似于memoize的函数(即其他装饰器),并且要求为每个arity函数复制每个函数是太多了。
在Scala中,使用什么类型来存储内存中的可变数据表?您可以使用类型-类方法来处理性问题。您仍然需要处理想要支持的每个函数属性,但不是每个属性/装饰器组合:
/**
* 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:
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
}
Library
使用Scalaz的scalaz.Memo
下面是一个类似于Aaron Novstrup的回答和这个博客的解决方案,除了一些更正/改进,简洁和更容易人们复制和粘贴的需要:)
import scala.Predef._
class Memoized[-T, +R](f: T => R) extends (T => R) {
import scala.collection.mutable
private[this] val vals = mutable.Map.empty[T, R]
def apply(x: T): R = vals.getOrElse(x, {
val y = f(x)
vals += ((x, y))
y
})
}
// TODO Use macros
// See si9n.com/treehugger/
// http://stackoverflow.com/questions/11400705/code-generation-with-scala
object Tupler {
implicit def t0t[R]: (() => R) => (Unit) => R = (f: () => R) => (_: Unit) => f()
implicit def t1t[T, R]: ((T) => R) => (T) => R = identity
implicit def t2t[T1, T2, R]: ((T1, T2) => R) => ((T1, T2)) => R = (_: (T1, T2) => R).tupled
implicit def t3t[T1, T2, T3, R]: ((T1, T2, T3) => R) => ((T1, T2, T3)) => R = (_: (T1, T2, T3) => R).tupled
implicit def t0u[R]: ((Unit) => R) => () => R = (f: Unit => R) => () => f(())
implicit def t1u[T, R]: ((T) => R) => (T) => R = identity
implicit def t2u[T1, T2, R]: (((T1, T2)) => R) => ((T1, T2) => R) = Function.untupled[T1, T2, R]
implicit def t3u[T1, T2, T3, R]: (((T1, T2, T3)) => R) => ((T1, T2, T3) => R) = Function.untupled[T1, T2, T3, R]
}
object Memoize {
final def apply[T, R, F](f: F)(implicit tupled: F => (T => R), untupled: (T => R) => F): F =
untupled(new Memoized(tupled(f)))
//I haven't yet made the implicit tupling magic for this yet
def recursive[T, R](f: (T, T => R) => R) = {
var yf: T => R = null
yf = Memoize(f(_, yf))
yf
}
}
object ExampleMemoize extends App {
val facMemoizable: (BigInt, BigInt => BigInt) => BigInt = (n: BigInt, f: BigInt => BigInt) => {
if (n == 0) 1
else n * f(n - 1)
}
val facMemoized = Memoize1.recursive(facMemoizable)
override def main(args: Array[String]) {
def myMethod(s: Int, i: Int, d: Double): Double = {
println("myMethod ran")
s + i + d
}
val myMethodMemoizedFunction: (Int, Int, Double) => Double = Memoize(myMethod _)
def myMethodMemoized(s: Int, i: Int, d: Double): Double = myMethodMemoizedFunction(s, i, d)
println("myMemoizedMethod(10, 5, 2.2) = " + myMethodMemoized(10, 5, 2.2))
println("myMemoizedMethod(10, 5, 2.2) = " + myMethodMemoized(10, 5, 2.2))
println("myMemoizedMethod(5, 5, 2.2) = " + myMethodMemoized(5, 5, 2.2))
println("myMemoizedMethod(5, 5, 2.2) = " + myMethodMemoized(5, 5, 2.2))
val myFunctionMemoized: (Int, Int, Double) => Double = Memoize((s: Int, i: Int, d: Double) => {
println("myFunction ran")
s * i + d + 3
})
println("myFunctionMemoized(10, 5, 2.2) = " + myFunctionMemoized(10, 5, 2.2))
println("myFunctionMemoized(10, 5, 2.2) = " + myFunctionMemoized(10, 5, 2.2))
println("myFunctionMemoized(7, 6, 3.2) = " + myFunctionMemoized(7, 6, 3.2))
println("myFunctionMemoized(7, 6, 3.2) = " + myFunctionMemoized(7, 6, 3.2))
}
}
当你运行ExampleMemoize时,你会得到:
myMethod ran
myMemoizedMethod(10, 5, 2.2) = 17.2
myMemoizedMethod(10, 5, 2.2) = 17.2
myMethod ran
myMemoizedMethod(5, 5, 2.2) = 12.2
myMemoizedMethod(5, 5, 2.2) = 12.2
myFunction ran
myFunctionMemoized(10, 5, 2.2) = 55.2
myFunctionMemoized(10, 5, 2.2) = 55.2
myFunction ran
myFunctionMemoized(7, 6, 3.2) = 48.2
myFunctionMemoized(7, 6, 3.2) = 48.2
我认为您可以这样做,然后使用DynamicProxy进行实际实现。
def memo[T<:Product, R, F <: { def tupled: T => R }](f: F )(implicit m: Manifest[F]):F
这个想法是由于函数缺少一个公共的超类型,我们使用结构类型来查找任何可以元组的东西(Function2-22,你仍然需要特殊的Function1)。
我把Manifest放在这里这样你就可以从函数特征F中构造DynamicProxy
元组还应该有助于记忆,例如您只需将元组放入Map[T,R]
这可以工作,因为K
可以是元组类型,所以memo(x,y,z) { function of x, y, z }
可以工作:
import scala.collection.mutable
def memo[K,R](k: K)(f: => R)(implicit m: mutable.Map[K,R]) = m.getOrElseUpdate(k, f)
隐式是我能看到的唯一干净地导入地图的方法:
implicit val fibMap = new mutable.HashMap[Int,Int]
def fib(x: Int): Int = memo(x) {
x match {
case 1 => 1
case 2 => 1
case n => fib(n - 2) + fib(n - 1)
}
}
感觉应该有可能以某种方式包装一个自动的HashMap[K,R]
,这样你就不必显式地创建fibMap
(并重新描述类型)