Variable number of types on a trait

Question

I'm creating a simple cache trait (to cache my functions easily):

trait Cache[A,B] {
  def _calc(v:A):B
  private var cache = Map[A,B]()
  def calc(v:A):B = {
    cache.get(v) match {
      case Some(x) => x
      case None => 
        val x = _calc(v)
        cache += (v -> x)
        x
    }
  }
}

The usage:

object Sol extends Cache[Int,Int] {
  def _calc(v:Int):Int = { /* do something here */ }
}
Sol.calc(5)

It works properly, but the problem arises when I need to cache functions with more arguments - so I need to develop traits Cache2, Cache3, all copy-pasting code from the first trait.

The possible workaround is to convert functions with multiple arguments to functions accepting a tuple, but that does not seem right.

Is there a way to do it more generally and to avoid DRY principle violation?

possible duplicate: [memoize a function](http://stackoverflow.com/questions/5875767/scala-memoize-a-function-no-matter-how-many-arguments-the-function-takes), [memoization](http://stackoverflow.com/questions/3640823/in-scala-2-8-what-type-to-use-to-store-an-in-memory-mutable-data-table) — kiritsuku, Nov 08 '11 at 20:15

score 3 · Answer 1 · answered Nov 08 '11 at 22:14

You could use a script to generate the scala source of your functions with different arities.

This approach may seem ugly, but it is used even on Scala library to define the source code of TupleN, ProductN and FunctionN (where N is an int smaller than 21).

om-nom-nom · Answer 2 · 2011-11-08T21:10:47.870

1

The possible solution is to use varargs for calc functions:

trait Cache[A,B] {
  def _calc(v:A*):B
  private var cache = Map[Seq[A],B]()
  def calc(v:A*):B = {
    cache.get(v.toList) match {
      case Some(x) => x
      case None => 
      val x = _calc(v:_*)
      cache += (v -> x)
      x
      }
   }
 }

object Sol1 extends Cache[Int,Int] {
  def _calc(v:Int*):Int = {
    require(v.length<2 && v.length>0, "use Sol2 for two-argument functions")
    v.head
  }
}
object Sol2 extends Cache[Int,(Int,Int)] {
  def _calc(v:Int*):(Int,Int) = {
    require(v.length<3 && v.length>1, "use Sol1 for single-argument functions")
    (v.head,v.last)
  }
}

But I do belive that there is cleaner and cleverer work around.

edited Nov 08 '11 at 21:10

answered Nov 08 '11 at 20:42

om-nom-nom

62,329
13
183
228

But this will only work for Lists of the same type. And you have to implement the functions to be cached so that they accept a List. – Silas Nov 08 '11 at 20:53
@Silas I've reworked implementation and now this is true varargs (but yes, arguments still has to share the same type). – om-nom-nom Nov 08 '11 at 21:12

Silas · Accepted Answer · 2011-11-08T21:06:04.477

You could at least automatically tuple your functions so that you can define the real function (for example add) accepting a usual parameter list:

object Add extends Cache[(Int, Int),Int]{
    def add (a:Int,b:Int):Int = a+b
    def _calc(t:(Int, Int)) = add _ tupled t
}

Call it via Add.calc(3, 5)

Edit: Or use this way to implement Cache2 ... CacheN without repeating the whole Cache code.

trait Cache2[A, B, C] extends Cache [(A,B), C] {
    def _calc2(a: A, b: B):C
    def _calc(t:(A,B)) = _calc2 _ tupled t
}

And again

object Add2 extends Cache2[Int,Int,Int] {
    def _calc2(a:Int, b:Int) = a+b
}

and Add2.calc(3, 5)

score 1 · Answer 4 · edited May 23 '17 at 10:34

I'm not entirely sure why you were disinclined to convert a function with multiple arguments to one that accepts a tuple, since you're presumably going to cache the arguments as a tuple anyway. The conversion can be entirely internal to the memoization implementation so that it has no effect on callers. This is exactly what the FunctionDecorator does:

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
}

When you apply a decorator (e.g., Memoize) to a function, it tuples the function, decorates the tupled function, and untuples the decorated function so that it can be called in the same way as the original function.

Of course, this shifts your DRY problem to the definition of Tuplers for all the function types. I would take paradigmatic's suggestion and use a script to define the Tuplers. Tuplers are far more useful than a bunch of CacheN types.

Variable number of types on a trait

4 Answers4