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

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

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

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

您正在使用currying进行多参数功能.这不是一种在Swift中表达事物的非常自然的方式,它使事情变得复杂. (Swift is not a functional programming language.)

正如您的链接文章所说,“所有教会数字都是带有两个参数的函数.”那样做吧.使它成为一个双参数功能.

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不是一种函数式语言;它以不同的方式分解问题.编写函数不是它的自然状态,因此语法的过度使用不应该让我们感到震惊.)如何实现？再向n施加一个f：

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

再说一次,总和的本质是什么？好吧,我们心情不好,所以这意味着它是一个功能,需要一个教会,并返回一个功能,并返回一个教会.

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

这里深刻的教训是教会类型的力量.当你试图将教会数字视为“等等等等等等的函数”时,你会很快迷失在咖喱和句法中.相反,将它们抽象为“教会数字”,并考虑每个功能应该采取和返回的内容.请记住,教会号始终是一个接受Int并返回Int的函数.无论嵌套多少次,它都不会增长或缩小.

值得在其他几个方向上采用这个例子,因为我们可以发表一些更深入的FP概念,以及Swift应该如何编写(这些都不一样……)

首先,用尖锐的风格写出教会数字是……不优雅的.感觉很糟糕.教会数量是根据功能构成而非应用来定义的,因此它们应该以无点的风格IMO编写.基本上,无论你在{x in …}}中看到{f},都只是丑陋且过度语法化.所以我们想要功能组合.好的,我们可以深入研究一些实验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.总结它们相当于功能组成.

但所有这一切,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