Есть ли общий способ запоминания в Scala?

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

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

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

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

Уровень класса/признака 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)
} 

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

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

Mutable HashMap не является потокобезопасным. Кроме того, определение операторов case отдельно для базовых условий кажется ненужной специальной обработкой, скорее Map может быть загружен с начальными значениями и передан в 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)

Вдохновение: Memoization, Глава 4 хороших частей Javascript Дугласа Крокфорда

ZIO#cached — это подход к запоминанию в ZIO.