4

我正在尝试在 Swift 3 中实现教堂数字。目前，我有：

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))

我不断收到一个编译时错误，即“关闭非转义参数'f'可能允许它转义”。作为快速修复，我接受了包含@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))
            }
        }
    }
4

2 回答 2

8

您正在为多参数函数使用柯里化。这不是在 Swift 中表达事物的一种非常自然的方式，它使事情变得复杂。（Swift 不是一种函数式编程语言。）

正如您链接的文章所说，“所有教堂数字都是带有两个参数的函数。” 就这样做吧。使其成为一个二参数函数。

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({$0 + 1}, 0)
}

只是在此基础上建立起来，你可以咖喱它（我想我只是在说@kennytm 也回答了）。Currying 在 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({$0 + 1})(0)
}

有一个非常合理的问题：“为什么我@escaping在第二种情况下需要，而在第一种情况下不需要？” 答案是当你在一个元组中传递函数时，你已经将它转义了（通过将它存储在另一个数据结构中），所以你不需要@escaping再次标记它。

对于您的进一步问题，使用 typealias极大地简化了这个问题，并帮助您更清楚地思考您的类型。

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

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什么？它需要一个教堂并返回一个教堂：

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什么？好吧，我们心情很不好，所以这意味着它是一个接受 Church 并返回一个接受 Church 并返回 Church 的函数的函数。

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)
        } } }
}

这里的深刻教训是Churchtypealias 的力量。当您尝试将 Church 数字视为“诸如此类的函数”时，您很快就会迷失在 curry 和语法中。取而代之的是，将它们抽象为“教会编号”，并考虑每个函数应该采用和返回什么。请记住，Church number始终是一个接受 Int 并返回 Int 的函数。无论嵌套多少次，它都不会因此而增长或缩小。

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

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

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($0)) }
}

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

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，我们更加有力地抓住了教会数字的本质。将它们相加相当于功能组合。

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

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

    static let zero: Church = Church{ _ in { $0 } }

    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{ $0 + 1 }(0)
    }
}

Int(Church(3) + Church(7).successor() + Church.zero) // 11
于 2016-10-03T17:10:20.500 回答
3

@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)

笔记：

  1. numToChurch即使没有@escaping零件，您的返回类型也是错误的。您缺少一个-> Int.

  2. 我在 中添加了基本n == 0情况numToChurch，否则将是无限递归。

  3. 由于结果numToChurch有一个转义闭包，因此也需要将相同的注释添加到churchToNum。

于 2016-10-03T17:17:06.457 回答