Swift 3 中的斐波那契数列生成器

Question

以下问答涵盖了在 Swift 中生成斐波那契数的一些方法，但它已经过时了（Swift 1.2？）：

• 使用 Functional Swift 的斐波那契项的总和

问题：我们如何使用现代 Swift (Swift >= 3) 巧妙地生成斐波那契数列？最好是避免显式递归的方法。

Answer 1

使用全局sequence(state:next:)函数

斯威夫特 3.0

作为另一种选择，我们可以使用一个简洁的全局sequence函数，一对在 Swift 3.0 中实现的函数（如进化提案SE-0094 中所述）。

• sequence(first:next:)
• sequence(state:next:)

使用后者，我们可以将斐波那契数列的先前和当前状态作为state的next闭包中的可变属性sequence(state:next:)。

func fibs(through: Int, includingZero useZero: Bool = false)
    -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: useZero ? (1, 0) : (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        guard pair.1 <= through else { return nil }
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        })
}
    // explicit type annotation of inout parameter closure
    // needed due to (current) limitation in Swift's type
    // inference

// alternatively, always start from one: drop useZero 
// conditional at 'state' initialization
func fibs1(through: Int)
    -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        guard pair.1 <= through else { return nil }
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        })
}

或者，使用 tuple hacks 压缩它（但是执行next一个额外的、不必要的时间）

func fibs(through: Int, includingZero useZero: Bool = false) -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: useZero ? (1, 0) : (0, 1), next: { 
        ($0.1 <= through ? $0.1 : Optional<Int>.none, $0 = ($0.1, $0.0 + $0.1)).0 })
}

func fibs1(through: Int) -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1), next: { 
        ($0.1 <= through ? $0.1 : Optional<Int>.none, $0 = ($0.1, $0.0 + $0.1)).0 })
}

请注意，nil当... <= through条件不再满足时，我们显式地终止序列并返回。

用法示例：

// fib numbers up through 50, excluding 0
fibs(through: 50).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34

// ... or
fibs1(through: 50).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34

// ... including 0
fibs(through: 50, includingZero: true).forEach { print($0) }
    // 0 1 1 2 3 5 8 13 21 34

// project Euler #2: sum of even fib numbers up to 4000000
print(fibs(through: 4_000_000)
    .reduce(0) { $1 % 2 == 0 ? $0 + $1 : $0 }) // 4 613 732

我们还可以从上面删除终止条件来构造一个无限的斐波那契数列，例如与 结合使用prefix：

func infFibs() -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1), next: {
        (pair: inout (Int, Int)) -> Int in (pair.1, pair = (pair.1, pair.0 + pair.1)).0 })
}

// prefix the first 6 fib numbers (excluding 0) from
// the infinite sequence of fib numbers
infFibs().prefix(10).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34 55

斯威夫特 3.1

当 Swift 3.1 到来时，prefix(while:)序列的方法，如进化提案SE-0045 中所述，将被实施。使用此附加功能，我们可以修改上述fibs方法以避免显式按nil条件序列终止：

func fibs(through: Int, startingFromZero useZero: Bool = false)
    -> AnySequence<Int> {
    return sequence(state: useZero ? (1, 0) : (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        }).prefix(while: { $0 <= through })
}

// alternatively, always start from one: drop useZero 
// conditional at 'state' initialization
func fibs1(through: Int) -> AnySequence<Int> {
    return sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        }).prefix(while: { $0 <= through })
}

示例应该与上面的 Swift 3.0 相同。

Answer 2

Swift 3.0 的另一种选择是使用辅助函数

public func sequence<T>(first: T, while condition: @escaping (T)-> Bool, next: @escaping (T) -> T) -> UnfoldSequence<T, T> {
    let nextState = { (state: inout T) -> T? in
        // Return `nil` if condition is no longer satisfied:
        guard condition(state) else { return nil }
        // Update current value _after_ returning from this call:
        defer { state = next(state) }
        // Return current value:
        return state
    }
    return sequence(state: first, next: nextState)
}

来自Express for 快速循环，具有动态范围：

for f in sequence(first: (0, 1), while: { $1 <= 50 }, next: { ($1, $0 + $1)}) {
    print(f.1)
}
// 1 1 2 3 5 8 13 21 34

注意，为了以包括所产生的序列中的零，只要更换的初始值(0, 1)由(1, 0)：

for f in sequence(first: (1, 0), while: { $1 <= 50 }, next: { ($1, $0 + $1)}) {
    print(f.1)
}
// 0 1 1 2 3 5 8 13 21 34

这使得“人工”检查

if pair.1 == 0 { pair.1 = 1; return 0 }

多余的。根本原因是斐波那契数可以推广到负指数（https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers）：

 ... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...