我最近在閱讀面向程式員的類別理論，在其中一個挑戰中，Bartosz 提議撰寫一個名為memoize的函式，該函式將函式作為引數并回傳相同的函式，不同之處在于，第一次呼叫這個新函式時，它存盤引數的結果，然后在每次再次呼叫時回傳此結果。
def memoize[A, B](f: A => B): A => B = ???
問題是，如果不求助于可變性，我想不出任何方法來實作這個功能。此外，我看到的實作使用可變資料結構來完成任務。
我的問題是，是否有一種純粹的功能性方式來實作這一點？也許沒有可變性或使用一些功能技巧？
感謝您閱讀我的問題和任何未來的幫助。祝你今天過得愉快！
uj5u.com熱心網友回復：
有沒有一種純粹的功能性方法來實作這一點？
不，不是最狹義的純函式和使用給定的簽名。
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：
[...] 功能
- 給定相同的輸入總是產生相同的結果
- 沒有副作用
被稱為純函式。
這真的是副作用嗎？
通常，至少在 Scala 中，內部狀態更改不被視為副作用。
請參閱Scala Book中的定義
純函式是僅依賴于其宣告的輸入及其內部演算法來產生其輸出的函式。它不會從“外部世界”（函式范圍之外的世界）讀取任何其他值，也不會修改外部世界中的任何值。
以下惰性計算示例都改變了它們的內部狀態，但通常仍然被認為是純函式式的，因為它們總是產生相同的結果并且除了內部狀態之外沒有副作用：
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))
}
Note that the cache is not public.
So, for a pure function f and without looking at memory consumption, timings, reflection or other evil stuff, you won't be able to tell from the outside whether f was called twice or g cached the result of f.
In this sense, side effects are only things like printing output, writing to public variables, files etc.
Thus, this implementation is considered pure (at least in Scala).
Avoiding mutable collections
If you really want to avoid var and mutable collections, you need to change the signature of your memoize method.
This is, because if g cannot change internal state, it won't be able to memoize anything new after it was initialized.
一個（低效但簡單）的例子是
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)）。
uj5u.com熱心網友回復：
讓我們試試（注意：我已經更改了 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)
uj5u.com熱心網友回復：
是的，有純粹的函式式方法來實作多型函式記憶。這個話題出奇地深，甚至召喚了米田引理，這很可能是 Bartosz 在這個練習中想到的。
Haskell 中的 Memoization博客文章通過稍微簡化問題給出了一個很好的介紹：它不是查看任意函式，而是將問題限制為整數函式。
以下 memoize 函式采用 Int -> a 型別的函式并回傳同一函式的 memoized 版本。訣竅是將函式轉換為值，因為在 Haskell 中，函式不是被記憶的，但值是被記憶的。memoize 將函式 f :: Int -> a 轉換為無限串列 [a]，其第 n 個元素包含 f n 的值。因此，由于惰性求值，串列的每個元素在第一次被 Haskell 運行時自動訪問和快取時都會被求值。
memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)
顯然，該方法可以推廣到任意域的功能。訣竅是想出一種方法，將域的型別用作用于“存盤”先前值的惰性資料結構的索引。這就是米田引理的用武之地，我對這個話題的理解變得脆弱。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/450956.html
上一篇：Sbt組裝插件生成一個空jar