如何在没有可变性的情况下在 Scala 中实现记忆？

Question

我最近在阅读面向程序员的范畴论，在其中一项挑战中，Bartosz 建议编写一个名为 memoize 的函数，该函数将一个函数作为参数，并且 returns 相同，不同之处在于，第一次调用此新函数时，它会存储参数的结果，然后 returns 每次再次调用时都会存储此结果。

def memoize[A, B](f: A => B): A => B = ???

问题是，我想不出有什么方法可以不借助可变性来实现这个功能。此外，我看到的实现使用可变数据结构来完成任务。

我的问题是，是否有一种纯粹的功能性方法来实现这一点？也许没有可变性或使用一些功能技巧？

感谢您阅读我的问题以及日后提供的任何帮助。祝你有美好的一天！

Answer 1

让我们try（注意：我已经更改了return类型的memoize来存储缓存数据）：

import scala.language.existentials

type M[A, B] = A => T forSome { type T <: (B, A => T) }

def memoize[A, B](f: A => B): M[A, B] = {
  import scala.collection.immutable
  
  def withCache(cache: immutable.Map[A, B]): M[A, B] = a => cache.get(a) match {
    case Some(b) => (b, withCache(cache))
    case None    =>
      val b = f(a)
      (b, withCache(cache + (a -> b)))
  }
  withCache(immutable.Map.empty)
}


def f(i: Int): Int = { print(s"Invoke f($i)"); i }


val (i0, m0) = memoize(f)(1)    // f only invoked at first time
val (i1, m1) = m0(1)
val (i2, m2) = m1(1)

Answer 2

is there a purely functional way of accomplishing this?

没有。不是最狭义的纯函数和使用给定的签名。

TLDR：使用可变集合，没问题！

`g`的杂质

val g = memoize(f)
// state 1
g(a)
// state 2

您希望通话 g(a) 发生什么？

如果 g(a) 记住结果，（内部）状态必须改变，所以调用 g(a) 之后的状态与之前不同。由于这可以从外部观察到，对 g 的调用有副作用，这使您的程序不纯。

从您引用的书中，2.5 Pure and Dirty Functions：

[...] functions that

always produce the same result given the same input and

have no side effects

are called pure functions.

这真的是副作用吗？

通常，至少在 Scala 中，内部状态变化不被视为副作用。

参见Scala Book

中的定义

A pure function is a function that depends only on its declared inputs and its internal algorithm to produce its output. It does not read any other values from “the outside world” — the world outside of the function’s scope — and it does not modify any values in the outside world.

以下惰性计算的示例都改变了它们的内部状态，但通常仍被认为是纯函数式的，因为它们总是产生相同的结果并且除了内部状态之外没有任何副作用：

lazy val x = 1
// state 1: x is not computed
x
// state 2: x is 1

val ll = LazyList.continually(0)
// state 1: ll = LazyList(<not computed>)
ll(0)
// state 2: ll = LazyList(0, <not computed>)

在您的情况下，等效项是使用私有的、可变的 Map（作为您可能已经找到的实现），例如：

def memoize[A, B](f: A => B): A => B = {
  val cache = mutable.Map.empty[A, B]
  (a: A) => cache.getOrElseUpdate(a, f(a))
}

注意缓存不是public。所以，对于一个纯函数 f 并且不查看内存消耗、时间、反射或其他邪恶的东西，你将无法从外部判断是否 f 被调用了两次或 g 缓存了 f.

的结果

从这个意义上说，副作用只是打印输出、写入 public 变量、文件等

因此，这个实现被认为是纯（至少在 Scala 中是这样）。

避免可变集合

如果您真的想要避免var和可变集合，您需要更改memoize方法的签名。这是因为如果 g 无法更改内部状态，它将无法在初始化后记忆任何新内容。

一个（低效但简单的）例子是

def memoizeOneValue[A, B](f: A => B)(a: A): (B, A => B) = {
  val b = f(a)
  val g = (v: A) => if (v == a) b else f(v)
  (b, g)
}

val (b1, g) = memoizeOneValue(f, a1)
val (b2, h) = memoizeOneValue(g, a2)
// ...

f(a1) 的结果将缓存在 g 中，但除此之外别无其他。然后，您可以链接它并始终获得新功能。

如果您对它的更快版本感兴趣，请参阅@esse 的答案，它的作用相同，但效率更高（使用不可变映射，因此 O(log(n)) 而不是上面的函数链表， O(n)).

Answer 3

是的，有实现多态函数记忆的纯函数方法。这个话题出奇地深奥，甚至召唤 Yoneda Lemma，这很可能是 Bartosz 在做这个练习时想到的。

博客 post Memoization in Haskell 通过稍微简化问题给出了一个很好的介绍：它不是查看任意函数，而是将问题限制为整数函数。

The following memoize function takes a function of type Int -> a and returns a memoized version of the same function. The trick is to turn a function into a value because, in Haskell, functions are not memoized but values are. memoize converts a function f :: Int -> a into an infinite list [a] whose nth element contains the value of f n. Thus each element of the list is evaluated when it is first accessed and cached automatically by the Haskell runtime thanks to lazy evaluation.

memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)

显然，该方法可以推广到任意域的功能。诀窍是想出一种方法，将域的类型用作用于“存储”先前值的惰性数据结构的索引。这是 where the Yoneda Lemma comes in 我自己对这个话题的理解变得脆弱。

如何在没有可变性的情况下在 Scala 中实现记忆？

How to implement memoization in Scala without mutability?

scala

thread-safety

immutability

memoization

category-theory

`g`的杂质

这真的是副作用吗？

避免可变集合

如何在没有可变性的情况下在 Scala 中实现记忆？

How to implement memoization in Scala without mutability?

scala

thread-safety

immutability

memoization

category-theory

g的杂质

这真的是副作用吗？

避免可变集合

`g`的杂质