pathikrit - 1 year ago 80

Scala Question

I wanted to memoize this:

`def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)`

println(fib(100)) // times out

So I wrote this and this surprisingly compiles and works (I am surprised because

`fib`

`case class Memo[A,B](f: A => B) extends (A => B) {`

private val cache = mutable.Map.empty[A, B]

def apply(x: A) = cache getOrElseUpdate (x, f(x))

}

val fib: Memo[Int, BigInt] = Memo {

case 0 => 0

case 1 => 1

case n => fib(n-1) + fib(n-2)

}

println(fib(100)) // prints 100th fibonacci number instantly

But when I try to declare fib inside of a

`def`

`def foo(n: Int) = {`

val fib: Memo[Int, BigInt] = Memo {

case 0 => 0

case 1 => 1

case n => fib(n-1) + fib(n-2)

}

fib(n)

}

Above fails to compile

`error: forward reference extends over definition of value fib`

case n => fib(n-1) + fib(n-2)

Why does declaring the

`val fib`

To clarify, why I might want to declare the recursive memoized function in the def scope - here is my solution to the subset sum problem:

`/**`

* Subset sum algorithm - can we achieve sum t using elements from s?

*

* @param s set of integers

* @param t target

* @return true iff there exists a subset of s that sums to t

*/

def subsetSum(s: Seq[Int], t: Int): Boolean = {

val max = s.scanLeft(0)((sum, i) => (sum + i) max sum) //max(i) = largest sum achievable from first i elements

val min = s.scanLeft(0)((sum, i) => (sum + i) min sum) //min(i) = smallest sum achievable from first i elements

val dp: Memo[(Int, Int), Boolean] = Memo { // dp(i,x) = can we achieve x using the first i elements?

case (_, 0) => true // 0 can always be achieved using empty set

case (0, _) => false // if empty set, non-zero cannot be achieved

case (i, x) if min(i) <= x && x <= max(i) => dp(i-1, x - s(i-1)) || dp(i-1, x) // try with/without s(i-1)

case _ => false // outside range otherwise

}

dp(s.length, t)

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

I found a better way to memoize using Scala:

```
def memoize[I, O](f: I => O): collection.Map[I, O] = new mutable.HashMap[I, O]() {
override def apply(key: I) = getOrElseUpdate(key, f(key))
}
```

Now you can write fibonacci as follows:

```
lazy val fib: Int => BigInt = memoize {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
```

Here's one with multiple arguments (the choose function):

```
lazy val c: ((Int, Int)) => BigInt = memoize {
case (_, 0) => 1
case (n, r) if r > n/2 => c(n, n - r)
case (n, r) => c(n - 1, r - 1) + c(n - 1, r)
}
```

And here's the subset sum problem:

```
// is there a subset of s which has sum = t
def isSubsetSumAchievable(s: Vector[Int], t: Int) = {
// f is (i, j) => Boolean i.e. can the first i elements of s add up to j
lazy val f: ((Int, Int)) => Boolean = memoize {
case (_, 0) => true // 0 can always be achieved using empty list
case (0, _) => false // we can never achieve non-zero if we have empty list
case (i, j) =>
val k = i - 1 // try the kth element
f(k, j - s(k)) || f(k, j)
}
f(s.length, t)
}
```

EDIT: As discussed below, here is a thread-safe version

```
def memoize[I, O](f: I => O): collection.Map[I, O] = new mutable.HashMap[I, O]() {self =>
override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key)))
}
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**