scala: memoriza una función sin importar cuántos argumentos tome la función?

Question

Quiero escribir una función memoize en scala que pueda aplicarse a cualquier objeto de función sin importar cuál sea el objeto de función. Quiero hacerlo de una manera que me permita usar una implementación única de memoize. Soy flexible con respecto a la sintaxis, pero lo ideal es que la memoria aparezca en algún lugar muy cerca de la declaración de la función, en lugar de después de la función. También me gustaría evitar declarar primero la función original y luego una segunda declaración para la versión memorizada.

así que alguna sintaxis ideal podría ser esta:

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

O incluso esto sería aceptable:

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

He visto formas de hacer esto donde se debe redefinir memoize para cada función de aridad, pero quiero evitar este enfoque. la razón es que necesitaré implementar docenas de funciones similares a memoize (es decir, otros decoradores) y es mucho pedir que se copien cada una para cada función de arity.

una forma de hacer memoize que requiere que repita las declaraciones de memoize (así que no es bueno) es en ¿Qué tipo usar para almacenar una tabla de datos mutables en memoria en Scala? .

Answer 1

Biblioteca

Usa el scalaz de scalaz.Memo

Manual

A continuación se muestra una solución similar a la respuesta de Aaron Novstrup y este blog , excepto con algunas correcciones / mejoras, brevedad y más fácil para las personas que copian y pegan las necesidades :)

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://.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))
  }
}

Cuando ejecute ExampleMemoize obtendrá:

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

Answer 2

Estaba pensando que podrías hacer algo como esto y luego usar un DynamicProxy para la implementación real.

def memo[T<:Product, R, F <: { def tupled: T => R }](f: F )(implicit m: Manifest[F]):F

La idea es que debido a que las funciones carecen de un supertipo común, utilizamos un tipo estructural para encontrar cualquier cosa que pueda ser tupleada (Función2-22, aún necesita la función de caso especial 1).

Tiro el Manifiesto allí para que puedas construir el DynamicProxy desde la función que es F

Tubling también debería ayudar con la memorización, ya que simplemente pones la tupla en un Mapa [T, R]

Answer 3

Esto funciona porque K puede ser un tipo de tupla, por lo que la memo(x,y,z) { function of x, y, z } funciona:

import scala.collection.mutable

def memo[K,R](k: K)(f: => R)(implicit m: mutable.Map[K,R]) = m.getOrElseUpdate(k, f)

Lo implícito era la única manera que podía ver para traer el mapa limpiamente:

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

Se siente como que debería ser posible envolver un HashMap[K,R] manera que no tenga que hacer fibMap (y volver a describir el tipo de forma explícita).

Answer 4

Puede utilizar un enfoque de clase de tipo para tratar el problema de la aridad. Aún tendrá que lidiar con cada función que desee apoyar, pero no para cada combinación de decoración / decorador:

/**
 * 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 continuación, puede implementar el decorador de la siguiente manera:

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

Su sintaxis "ideal" no funcionará porque el compilador supondría que el bloque pasado a memoize es un cierre léxico de 0 argumentos. Sin embargo, puedes usar tu última sintaxis:

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

Editar:

Para eliminar una gran cantidad de elementos para definir nuevos decoradores, puede crear un rasgo:

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
}

Esto le permite redefinir el decorador Memoize como

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

En lugar de invocar un método memoize en el objeto Memoize, aplica el objeto Memoize directamente:

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

o

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