在 Swift 3 中实施教会数字时出现非转义错误

Question

我正在尝试在 Swift 3 中实现 Church Numerals。目前，我有：

func numToChurch(n: Int) -> ((Int) -> Int) -> Int {

    return { (f: (Int) -> Int) -> (Int) -> Int in
        return { (x : Int) -> Int in
            return f(numToChurch(n: n - 1)(f)(x))
        }
    }
}

func churchToNum(f: ((Int) -> Int) -> (Int)-> Int) -> Int {
    return f({ (i : Int) -> Int in
        return i + 1
    })(0)
}

在我的函数 numToChurch 的这一行：

return f(numToChurch(n: n - 1)(f)(x))

我不断收到 "Closure of non-escaping parameter 'f' may allow it to escape" 的编译时错误。作为快速修复，我接受了建议的更改以包括 @escaping:

func numToChurch(n: Int) -> ((Int) -> Int) -> Int {

    return { (f: @escaping (Int) -> Int) -> (Int) -> Int in
        return { (x : Int) -> Int in
            return f(numToChurch(n: n - 1)(f)(x))
        }
    }
}

但即使在进行更改后，我仍不断收到相同的错误提示，它建议在 "f:" 之后添加另一个 @escaping。我知道这与将函数参数标记为 @escaping 以告诉编译器可以存储或捕获参数以进行函数式编程有关。但是我不明白为什么我总是收到这个错误。

原非转义问题已解决

帮助理解 Swift 中的教堂编码：

func zero(_f: Int) -> (Int) -> Int {
    return { (x: Int) -> Int in
        return x
    }
}

func one(f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { (x: Int) in
        return f(x)
    }
}

func two(f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { (x: Int) in
        return f(f(x))
    }
}

func succ(_ f: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
    return { (f : @escaping ((Int) -> Int)) -> Int in
        return { (x : Int) -> Int in
            return f(n(f)(x))
        }
    }
}


func sum(m: @escaping ((Int) -> (Int) -> Int)) -> ((Int) -> (Int) -> Int) -> (Int) -> (Int) -> Int {
    return { (n: @escaping ((Int) -> Int)) -> (Int) -> (Int) -> Int in
        return { (f: Int) -> (Int) -> Int in
            return { (x: Int) -> Int in
                return m(f)(n(f)(x))
            }
        }
    }

Answer 1

您正在对多参数函数使用柯里化。这不是用 Swift 表达事物的一种非常自然的方式，而且它使事情变得复杂。 (Swift is not a functional programming language.)

正如您链接的文章所说，"All Church numerals are functions that take two parameters."那就这样做吧。使它成为一个二参数函数。

typealias Church = (_ f: ((Int) -> Int), _ x: Int) -> Int

这是一个有两个参数的函数，一个函数及其参数。

现在你想在函数中将参数包装 N 次:

// You could probably write this iteratively, but it is pretty elegant recursively 
func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return { (_, n) in n } }

    // Otherwise, recursively apply the function
    return { (f, x) in
        numToChurch(n - 1)(f, f(x))
    }
}

返回只是应用函数：

func churchToNum(_ church: Church) -> Int {
    return church({[=12=] + 1}, 0)
}

在此基础上，您可以咖喱它（我想我只是在说@kennytm 也回答过的问题）。 Swift:

中的柯里化稍微复杂一点

typealias Church = (@escaping (Int) -> Int) -> (Int) -> Int

func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return { _ in { n in n } } }

    return { f in { x in
        numToChurch(n - 1)(f)(f(x))
        }
    }
}

func churchToNum(_ church: Church) -> Int {
    return church({[=13=] + 1})(0)
}

有一个非常合理的问题："Why do I need @escaping in the second case, but not in the first?"答案是当你在元组中传递函数时，你已经将它转义了（通过将它存储在另一个数据结构中），所以你不需要需要重新标记@escaping

对于您进一步的问题，使用类型别名戏剧性地 可以简化此问题并帮助您更清楚地思考您的类型。

那么零的参数是什么？没有什么。这是一个常数。那么它的签名应该是什么？

func zero() -> Church

我们如何实施它？我们应用 f 零次

func zero() -> Church {
    return { f in { x in
        x
        } }
}

一和二几乎相同：

func one() -> Church {
    return { f in { x in
        f(x)
        } }
}

func two() -> Church {
    return { f in { x in
        f(f(x))
        } }
}

succ的签名是什么？它需要一个教堂和 return 一个教堂：

func succ(_ n: @escaping Church) -> Church {

因为这是 Swift，我们需要通过添加 @escaping 和 _ 来让事情变得更自然。（Swift不是函数式语言，它分解问题的方式不同。组合函数不是它的自然状态，所以语法的过度丰富不应该让我们感到震惊。）如何实现？再应用一个 f 到 n:

func succ(_ n: @escaping Church) -> Church {
    return { f in { x in
        let nValue = n(f)(x)
        return f(nValue)
        } }
}

再一次，sum 的性质是什么？好吧，我们正处于一种柯里化的情绪中，所以这意味着它是一个函数，它接受一个教堂，returns 一个函数接受一个教堂，returns 一个教堂。

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church

同样，需要一些额外的语法，因为 Swift。（和上面一样，我添加了一个额外的 let 绑定只是为了让这些部分更清晰。）

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church {
    return { m in { f in { x in
        let nValue = n(f)(x)
        return m(f)(nValue)
        } } }
}

这里的深刻教训是 Church typealias 的强大功能。当您尝试将教会数字视为 "functions that blah blah blah" 时，您很快就会迷失在 curry 和语法中。相反，将它们抽象为 "Church numbers" 并考虑每个函数应该采用什么和 return。请记住，教堂号码总是一个采用 Int 和 returns 一个 Int 的函数。无论嵌套多少次，它都不会变大或变小。

值得在其他几个方向上使用这个例子，因为我们可以发挥 FP 的一些更深层次的想法，以及 Swift 应该如何真正编写（它们不一样....）

首先，用尖锐的字体书写教会数字是……不雅观的。感觉很糟糕。教堂号码是根据功能组合而不是应用程序定义的，因此它们应该以无点风格的 IMO 编写。基本上，在任何你看到 { f in { x in ...} } 的地方，它都是丑陋的和过度语法化的。所以我们需要功能组合。好的，我们可以深入研究一些实验性的 stdlib features 并得到

infix operator ∘ : CompositionPrecedence

precedencegroup CompositionPrecedence {
    associativity: left
    higherThan: TernaryPrecedence
}

public func ∘<T, U, V>(g: @escaping (U) -> V, f: @escaping (T) -> U) -> ((T) -> V) {
    return { g(f([=21=])) }
}

现在，这对我们有什么用？

func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return zero() }
    return { f in f ∘ numToChurch(n - 1)(f) }
}

func succ(_ n: @escaping Church) -> Church {
    return { f in f ∘ n(f) }
}

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church {
    return { m in { f in
        n(f) ∘ m(f)
        } }
}

所以我们不需要再谈论 x 了。国际海事组织，我们更有力地抓住了教会人数的本质。将它们相加相当于函数组合。

但话虽如此，IMO 这并不好 Swift。 Swift 需要结构和方法，而不是函数。它绝对不想要一个名为 zero() 的顶级函数。太可怕了Swift。那么我们如何在 Swift 中实现教堂编号？通过提升成一个类型。

struct Church {
    typealias F = (@escaping (Int) -> Int) -> (Int) -> Int
    let applying: F

    static let zero: Church = Church{ _ in { [=23=] } }

    func successor() -> Church {
        return Church{ f in f ∘ self.applying(f) }
    }

    static func + (lhs: Church, rhs: Church) -> Church {
        return Church{ f in lhs.applying(f) ∘ rhs.applying(f) }
    }
}

extension Church {
    init(_ n: Int) {
        if n <= 0 { self = .zero }
        else { applying = { f in f ∘ Church(n - 1).applying(f) } }
    }
}

extension Int {
    init(_ church: Church) {
        self = church.applying{ [=23=] + 1 }(0)
    }
}

Int(Church(3) + Church(7).successor() + Church.zero) // 11

Answer 2

@escaping 是参数类型的一部分，所以你需要这样做：

func numToChurch(n: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
//                           ^~~~~~~~~

完整的工作代码：

func numToChurch(n: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
//                           ^~~~~~~~~                        ^~~~~~
    return { (f: @escaping (Int) -> Int) -> (Int) -> Int in
//               ^~~~~~~~~
        if n == 0 {
            return { x in x }
        } else {
            return { (x : Int) -> Int in
                return f(numToChurch(n: n - 1)(f)(x))
            }
        }
    }
}

func churchToNum(f: (@escaping (Int) -> Int) -> (Int) -> Int) -> Int {
//                   ^~~~~~~~~
    return f({ (i : Int) -> Int in
        return i + 1
    })(0)
}

let church = numToChurch(n: 4)
let num = churchToNum(f: church)

注：

即使没有 @escaping 部分，您 numToChurch 的 return 类型也是错误的。您缺少 -> Int.
我在numToChurch中添加了基础n == 0的情况，否则会无限递归。
由于numToChurch的结果有一个转义闭包，所以churchToNum的结果也需要添加相同的注解。

在 Swift 3 中实施教会数字时出现非转义错误

Non-escaping error when implementing Church Numerals in Swift 3

functional-programming

church-encoding

church

swift

swift3