需要Swift中Memoize实现的详细说明(WWDC 14,会话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函数只需要调用一次,因为它将任何函数(正确类型)转换为该函数的memoized版本.从那时起,您只需调用memoized版本.所以这是一个接受函数作为参数并返回一个新函数作为结果的函数.返回的函数只是调用我在前一段中描述的memoization中的原始函数.

很难知道还有什么要告诉你,因为我不知道你发现哪些部分难以理解.我的书详细介绍了如何在Swift中传递函数.如果您不理解将函数作为参数传递给函数的概念,请阅读本节.如果您不理解返回函数的函数的概念,请阅读本节.

Swift有闭包,所以我们在返回函数的环境空间中维护字典(通过在返回函数之外定义它,以便捕获它).如果你发现这很难理解,这里有一个更简单的例子.