# Scala Single Generic Parameter Function Memoization

a guest
Aug 24th, 2015
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2. The following code was created on the basis of Michid's Weblog https://michid.wordpress.com/2009/02/23/function_mem/
3. and influenced by Daniel Spiewak's comment.
4.
5. From what I understand, because of this implementation of Memoization, tail recursion compilation cannot be applied.
6. As a result it is possible to have a StackOverflowError (try: fibonacci(250000)).  This can be avoided if the calculations are performed from the base cases up, instead of final case down to the base cases.
7.
8. A bad solution to this that I can think of would be to check if the value is over a certain size (say 1000) and then calculate up from there. Below is a bad implementation of this idea.
9.
10. Hugh Kaznowski
11. */
12. object Solution {
13.
14.   class Memoize[-I, +O](f: (I, I=>O) => O) {
15.     private[this] val cache = scala.collection.mutable.Map[I, O]();
16.     def apply(i: I): O = {
17.       if (cache.contains(i))
18.         cache(i)
19.       else {
20.         println(s"Calculating for \$i")
21.         val ret = f(i, apply)
22.         cache.put(i, ret)
23.         ret
24.       }
25.     }
26.   }
27.
28.   def fib(v: Int, f: (Int=>Int)): Int = {
29.     if (v<3)
30.       1
31.     else
32.       f(v-2)+f(v-1)
33.   }
34.
35.   def badfib(v: Int, f: (Int=>Int)): Int = { // Can definitely be optimized
36.     if (v>1000)
37.       Range(v/2, v-2).foreach(f(_))
38.     if (v<3)
39.       1
40.     else
41.       f(v-2)+f(v-1)
42.   }
43.
44.   def main(args: Array[String]): Unit = {
45.     val fibonacci = new Memoize(fib)
46.     val bfibonacci = new Memoize(badfib)
47.
48.     bfibonacci(2500000) // This will take a long time
49.     println("-------------")
50.     bfibonacci(26)
51.   }
52. }