swift - 需要详细解释 Swift 中的 Memoize 实现(WWDC 14， session 404)

Question

Dave Abrahams 展示了一个非常有趣的 memoize 版本 (WWDC 2014 Session 404: Advanced Swift):

func Memoize<T:Hashable, U> (body: (T -> U, T ) -> U ) -> (T) -> U {

      var memo = Dictionary <T, U> ()

      var result: (T -> U)!

      result = { x in
            if let q = memo[x] { return q }
            let r = body(result, x)
            memo[x] = r
            return r
      }

      return result
}

let factorial = Memoize { (factorial, x) in
                x == 0 ? 1 : x * factorial(x - 1)
        }

=====即使对于递归函数，这也很有效。我很难真正理解这一点。任何专家解释都会有很大帮助。

更新:使用局部函数:

Swift 2 的本地函数允许更干净地实现 Memoize。

Swift 3 需要 @noescaping 注解；否则它会提示:“关闭非转义参数 body 的声明可能允许它转义。”

func Memoize<T:Hashable, U> (body: @escaping ((T) -> U, T ) -> U ) -> (T) -> U {

    var memo = Dictionary <T, U> ()

    func result(x : T) -> U {
        if let q = memo[x] { return q }
        let r = body(result, x)
        memo[x] = r
        return r
    }

    return result
}

Answer 1

它实际上是一个或多或少完全标准的 memoize 实现。您保留输入和输出的映射(此处为字典)。如果我们已经在字典中有了输入，查找它并返回输出。如果我们不这样做，计算它，将它存储在字典中，然后返回它。

memoize 函数只需调用一次，因为它将任何函数(适当类型的)转换为该函数的内存版本。从那时起，您只需调用内存版本。所以这是一个接受一个函数作为参数并返回一个新函数作为结果的函数。返回的函数简单地包装了对我在上一段中描述的内存中的原始函数的调用。

很难知道还能告诉您什么，因为我不知道您觉得哪一部分难以理解。我的书详细介绍了函数如何在 Swift 中传递。如果您不理解将函数作为参数传递给函数的概念，请阅读 this section .如果您不理解函数返回函数的概念，请阅读 this section .

Swift 有闭包，所以我们可以在返回函数的环境空间中维护字典(通过在返回函数外定义它，以便捕获它)。如果那是您觉得难以理解的内容，这里有一个 simpler example