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

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

我不断收到编译时错误"关闭非转义参数'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 cont中的教会编码:

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

您正在使用currying进行多参数功能.这不是一种在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也回答了什么).在Swift中,Currying稍微复杂一些:

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.当你试图将教会数字视为"等等等等等等的函数"时,你会很快迷失在咖喱和句法中.相反,将它们抽象为"教会数字",并考虑每个功能应该采取和返回的内容.请记住,教会号始终是一个接受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想要结构和方法,而不是函数.它肯定不希望调用顶级函数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