Scala:部分评估函数并缓存固定值

Question

有没有一种简单的方法可以以纯函数方式缓存部分应用函数的固定值。

代码示例:

scala> def f(x:Int,y:Int)={
    def expensiveCalculation(num:Int)={
        println("I've spent a lot of time(!) calculating square of "+num)
        num*num
    }
    lazy val x2=expensiveCalculation(x)
    lazy val y2=expensiveCalculation(y)
    lazy val r=x2+y2
    r
}

scala> def g=f(1,_:Int)

scala> g(2)
I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
res18: Int = 5

scala> g(3)
I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 3
res19: Int = 10

但我不希望为 num=1 调用两次昂贵的计算。 .由于昂贵的计算没有副作用，所以保存结果没有问题(请不要在我的示例代码中考虑在输出流上打印的副作用)。

我可以通过手动保存状态来实现我正在寻找的使用 OOP 风格的东西(尽管如果你想为它编写一个通用的可重用代码，它不是很干净)。

我认为在每个函数都没有副作用的 FP 中，实现这个目标应该更容易。实际上，我想不出在纯函数式语言中将其用作默认行为的严格限制(除了一些实际问题，例如缓存所需的内存量等)。

Answer 1

您可以利用 Scala 同时是 OOP 和 FP 语言以及 Scala 中的函数是对象这一事实。

object CachedFunction extends App {

  val f = new Function2[Int, Int, Int] {
    def expensiveCalculation(num: Int) = {
      println("I've spent a lot of time(!) calculating square of " + num)
      num * num
    }

    var precomputed: Map[Int, Int] = Map()

    def getOrUpdate(key: Int): Int =
      precomputed.get(key) match {
        case Some(v) => v
        case None =>
          val newV = expensiveCalculation(key)
          precomputed += key -> newV
          newV
      }

    def apply(x: Int, y: Int): Int =
      getOrUpdate(x) + getOrUpdate(y)
  }

  def g = f(1, _: Int)

  g(2)
  g(3)
  g(3)
  f(1, 2)
}

打印:

I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
I've spent a lot of time(!) calculating square of 3

我已更改 f来自 def至val - 这允许 f 成为一个“存储”函数的对象，而不仅仅是一个每次都运行其整个主体的方法。在这种情况下只有 apply每次运行并保留函数对象的实例变量。其余的是 OOPish 方式。

虽然这对于调用者来说可以被认为是不可变的，因为返回的结果不会随着时间的推移而改变，但它不是线程安全的。您可能希望使用某种同步映射来存储缓存值。

编辑:
在我写完这篇文章后，我搜索了“函数内存”并得到了这些类似的解决方案。虽然它们更通用:

Scala Memoization: How does this Scala memo work?

Is there a generic way to memoize in Scala?

http://eed3si9n.com/learning-scalaz-day16

显然Scalaz中甚至还有一些东西:)

编辑:

问题是即使函数被部分应用或柯里化(Currying)，Scala 也不会急切地评估函数的参数。它只是存储参数的值。这是一个例子:

object CachedArg extends App {

  def expensiveCalculation(num: Int) = {
    println("I've spent a lot of time(!) calculating square of " + num)
    num * num
  }

  val ff: Int => Int => Int = a => b => expensiveCalculation(a) + expensiveCalculation(b)
  val f1 = ff(1) // prints nothing

  val e1 = expensiveCalculation(1) // prints for 1
  val f: (Int, Int) => Int = _ + expensiveCalculation(_)
  val g1 = f(e1, _: Int)
  g1(2) // does not recalculate for 1 obviously
  g1(3)
}

打印:

I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
I've spent a lot of time(!) calculating square of 3

这表明您仍然可以手动评估一次参数并通过将其部分应用于函数(或柯里化(Currying))来“保存”它。我想这就是你所追求的。为了有更方便的方式，您可以使用这种方法:

object CachedFunction extends App {

  val f = new Function1[Int, Int => Int] {
    def expensiveCalculation(num: Int) = {
      println("I've spent a lot of time(!) calculating square of " + num)
      num * num
    }

    def apply(x: Int) =
      new Function[Int, Int] {
        val xe = expensiveCalculation(x)

        def apply(y: Int) = xe + expensiveCalculation(y)
      }
  }

  val g1 = f(1) // prints here for eval of 1
  g1(2)
  g1(3)
}

打印:

I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
I've spent a lot of time(!) calculating square of 3

但是，在最后两个示例中，memoizaition 是函数对象的本地化。您必须重用相同的函数对象才能使其工作。与此不同的是，在第一个示例中，memoizaition 对于定义函数的范围是全局的。