[SCALA] 스칼라 : 상관없이 함수가 걸리는 많은 인수 기능을 memoize하지?

스칼라 : 상관없이 함수가 걸리는 많은 인수 기능을 memoize하지?

내가 아무리 그 함수 객체가 무엇인지 어떤 함수 객체에 적용 할 수 없습니다 스칼라에서 memoize 함수를 작성하려고합니다. 나는 나를 memoize의 하나의 구현을 사용 할 수있는 방법으로 그렇게하고 싶다. 내가 구문에 대한 유연 해요,하지만 이상적으로 memoize 매우 가까운 기능 후에 반대로 함수의 선언 어딘가 나타납니다. 저는 원래 기능하고 memoized 버전 제 선언 선언 제 피하고자도 것이다.

그래서 어떤 이상적인 구문이 될 수 있습니다

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에 유사한 기능 (즉, 다른 장식 자) 수십를 구현해야한다는 것입니다 및 각 인수에 대응 기능에 대한 각 하나를 복사해야하는 무리한 요구입니다.

한 가지 방법은 memoize가 (이 더 좋은 없습니다 그래서) 스칼라에서 메모리 가변 데이터 테이블을 저장하기 위해 사용하는 어떤 종류의에 있습니다 memoize 선언을 반복 할 필요합니까해야 할 일?

해결법

1. ==============================

   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
   }
   

2. ==============================

   2.사용 Scalaz의 scalaz.Memo

   사용 Scalaz의 scalaz.Memo

   다음은 아론 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
   

3. ==============================

   3.나는이 같은 실제 구현을위한 사용 DynamicProxy보다 뭔가를 할 수 있다고 생각했다.

   나는이 같은 실제 구현을위한 사용 DynamicProxy보다 뭔가를 할 수 있다고 생각했다.

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

   기능은 공통의 슈퍼 타입이 부족하기 때문에 우리가 tupled 할 수있는 일 찾기 위해 구조 유형을 사용하는 것이되는 아이디어 (기능 2.22는, 당신은 여전히 ​​특별한 경우 기능 1)가 필요합니다.

   당신이 F 인 기능 특성에서 DynamicProxy을 구성 할 수 있도록 내가 거기에 매니페스트를 던져

   Tupling해야 또한 간단한 넣어 같은 메모이 제이션에 대한 도움말지도 [T, R]의 튜플

4. ==============================

   4.메모 (X, Y, Z) {X, Y, Z의 함수}이 작동되도록 작품 K 튜플 유형이 될 수 있기 때문 :

   메모 (X, Y, Z) {X, Y, Z의 함수}이 작동되도록 작품 K 튜플 유형이 될 수 있기 때문 :

   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을 할 필요가 없습니다 (및 유형을 재-설명).

from https://stackoverflow.com/questions/5875767/scala-memoize-a-function-no-matter-how-many-arguments-the-function-takes by cc-by-sa and MIT license