在Swift 3中实现Church Numerals时出现非转义错误

13z8s7eq  于 2023-09-30  发布在  Swift
关注(0)|答案(2)|浏览(92)

我正在尝试在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中的church编码续:

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

xmakbtuz1#

你正在对多参数函数使用currying。在Swift中,这不是一种非常自然的表达方式,它使事情变得复杂。(Swift is not a functional programming language.)
正如你链接的文章所说,“所有教会数字都是带两个参数的函数。”使其成为两个参数函数。

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

这是一个有两个参数的函数,一个函数和它的参数。
现在你想把参数 Package 在函数中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
对于你进一步的问题,使用类型别名 * 极大地 * 简化了这个问题,并帮助你更清楚地思考你的类型。
零的参数是什么?什么都没有。这是个常数。那么它的签名应该是什么呢?

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的性质是什么?好吧,我们现在的心情很好,这意味着它是一个函数,它接受一个教堂,然后返回一个函数,它接受一个教堂,然后返回一个教堂。

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类型别名的强大功能。当你试着把Church数想象成“诸如此类的函数”时,你很快就会迷失在咖喱和语法中。相反,将它们抽象为“教会数”,并考虑每个函数应该获取和返回什么。记住,Church数 * 总是 * 一个接受Int并返回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($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。将它们相加等价于函数合成。
但所有这一切都说,海事组织这不是伟大的斯威夫特。Swift需要的是结构和方法,而不是函数。它肯定不想要一个名为zero()的顶级函数。这是可怕的斯威夫特。那么,我们如何在Swift中实现Church数字呢?通过提升到一个类型。

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
ulydmbyx

ulydmbyx2#

@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.即使没有@escaping部分,numToChurch的返回类型也是错误的。您缺少-> Int
1.我已经在numToChurch中添加了基本的n == 0情况,否则它将是一个无限递归。
1.由于numToChurch的结果有一个转义闭包,因此也需要向churchToNum的结果添加相同的注解。

相关问题