Существует ли общий способ memoize в Scala?

Я хотел бы запомнить это:

def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)
println(fib(100)) // times out

Итак, я написал это, и это удивительно компилируется и работает (я удивлен, потому что 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

Но когда я пытаюсь объявить фиб внутри 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)
}

Выше не удается скомпилировать error: forward reference extends over definition of value fib case n => fib(n-1) + fib(n-2)

Почему объявляется val fib внутри def, но не работает в области класса/объекта?

Чтобы пояснить, почему я могу захотеть объявить рекурсивную memoized функцию в области def - вот мое решение проблемы суммирования подмножества:

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

Ответ 1

Я нашел лучший способ memoize с помощью Scala:

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

Теперь вы можете написать fibonacci следующим образом:

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

Здесь один с несколькими аргументами (функция выбора):

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)
}

И здесь проблема суммы подмножества:

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

РЕДАКТИРОВАТЬ: Как описано ниже, здесь приведена нить-безопасная версия

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

Ответ 2

Уровень класса/уровня val компилируется в комбинацию метода и частной переменной. Следовательно, допускается рекурсивное определение.

Локальные val, с другой стороны, являются просто регулярными переменными, и поэтому рекурсивное определение не допускается.

Кстати, даже если def, который вы определили, работал, он не будет делать то, что вы ожидаете. При каждом вызове foo будет создан новый объект функции fib, и он будет иметь свою собственную карту поддержки. Вместо этого вы должны это делать (если вы действительно хотите, чтобы ) был def):

private val fib: Memo[Int, BigInt] = Memo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2) 
}

def foo(n: Int) = {
  fib(n)
}

Ответ 3

У Scalaz есть решение для этого, почему бы не использовать его повторно?

import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-2) + fib(n-1)
}

Вы можете узнать больше о memoization в Scalaz.

Ответ 4

Mutable HashMap не является потокобезопасным. Кроме того, определение операторов case отдельно для базовых условий кажется ненужной специальной обработкой, а Map может быть загружен с начальными значениями и передан Memoizer. Ниже следует подпись Memoizer, в которой он принимает памятку (неизменяемую карту) и формулу и возвращает рекурсивную функцию.

Memoizer будет выглядеть как

def memoize[I,O](memo: Map[I, O], formula: (I => O, I) => O): I => O

Теперь, учитывая следующую формулу Фибоначчи,

def fib(f: Int => Int, n: Int) = f(n-1) + f(n-2)

Фибоначчи с Memoizer могут быть определены как

val fibonacci = memoize( Map(0 -> 0, 1 -> 1), fib)

где контекстный агностический универсальный Memoizer определяется как

    def memoize[I, O](map: Map[I, O], formula: (I => O, I) => O): I => O = {
        var memo = map
        def recur(n: I): O = {
          if( memo contains n) {
            memo(n) 
          } else {
            val result = formula(recur, n)
            memo += (n -> result)
            result
          }
        }
        recur
      }

Аналогично, для факториала формула

def fac(f: Int => Int, n: Int): Int = n * f(n-1)

и факториал с Memoizer

val factorial = memoize( Map(0 -> 1, 1 -> 1), fac)

Вдохновение: памятка, глава 4 Javascript, хорошие детали Дугласа Крокфорда