scala: запоминать функцию независимо от того, сколько аргументов она принимает?

Question

Я хочу написать функцию напоминания в Scala, которая может быть применена к любому функциональному объекту независимо от того, что это за функциональный объект.Я хочу сделать это таким образом, чтобы я мог использовать одну реализацию 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 должен быть переопределен для каждой функции arity, но я хочу избежать этого подхода.причина в том, что мне нужно будет реализовать десятки функций, аналогичных memoize (то есть другим декораторам), и слишком много нужно просить скопировать каждую из них для каждой функции arity.

один способ сделать memoize, которыйпотребовать от вас повторить объявления памятки (так что это бесполезно) в Какой тип использовать для хранения таблицы изменяемых данных в памяти в Scala? .

Answer 1

Вы можете использовать подход типа класса для решения проблемы арности.Вам все равно придется иметь дело с каждой функцией арности, которую вы хотите поддерживать, но не для каждой комбинации арити / декоратора:

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

Answer 2

Библиотека

Использование Scalaz scalaz.Memo

Руководство

Ниже приведено решение, аналогичное ответу Аарона Новструпа и этого блога , за исключением некоторыхисправления / улучшения, краткость и упрощение потребностей пользователей в копировании и вставке:)

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

Answer 3

Я думал, что вы могли бы сделать что-то подобное, а затем использовать DynamicProxy для фактической реализации.

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

Идея состоит в том, что, поскольку функциям не хватает общего супертипа, мы используем структурный тип, чтобы найтивсе, что может быть кортежем (функция 2-22, вам все еще нужен особый случай, функция 1).

Я добавляю туда манифест, чтобы вы могли создать DynamicProxy из свойства функции F

Кортеж также должен помочь с запоминанием, как если бы вы просто помещали кортеж в карту [T, R]

Answer 4

Это работает, потому что 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 (и заново описывать тип).