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

我正在尝试学习函数式 Swift，并开始从 Project Euler 做一些练习。

甚至斐波那契数列 问题2 斐波那契数列中的每一项新项都是通过添加前两项而生成的。从 1 和 2 开始，前 10 项将是：

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

通过考虑斐波那契数列中值不超过四百万的项，求偶数项的总和。

根据 WWDC 高级 Swift 视频实现了记忆斐波那契函数：

func memoize<T:Hashable, U>( body: ((T)->U,T) -> U) -> (T)->U {
  var memo = [T:U]()
  var result: ((T)->U)!
  result = { x in
    if let q = memo[x] { return q }
    let r = body(result,x)
    memo[x] = r
    return r
  }
  return result
}

let fibonacci = memoize { (fibonacci:Int->Double,n:Int) in n < 2 ? Double(n) : fibonacci(n-1) + fibonacci(n-2) }

并实现了一个符合以下条件的类Sequence协议

class FibonacciSequence: SequenceType {
  func generate() -> GeneratorOf<Double> {
      var n = 0
      return GeneratorOf<Double> { fibonacci(n++) }
  }

  subscript(n: Int) -> Double {
      return fibonacci(n)
  }
}

问题的第一个（非功能性）解决方案：

var fib = FibonacciSequence().generate()
var n:Double = 0
var sum:Double = 0
while n < Double(4_000_000) {
  if n % 2 == 0 {
    sum += n
  }
n = fib.next()!
}

println(sum)

第二种更实用的解决方案，使用ExSwift因为它的takeWhile功能

let f = FibonacciSequence()
println((1...40).map { f[$0] }
                .filter { $0 % 2 == 0 }
                .takeWhile { $0 < 4_000_000 }
                .reduce(0, combine: +))

我想改进这个解决方案，因为1...40范围无缘无故地计算了太多项。理想情况下，我希望能够有某种无限范围，但同时只计算满足条件的所需项takeWhile

有什么建议 ？

在这里，我生成了一旦达到最大值就已经停止的序列。 那么你只需要减少不过滤，只需和0时n is odd.

func fibonacciTo(max: Int) -> SequenceOf<Int> {
    return SequenceOf { _ -> GeneratorOf<Int> in
        var (a, b) = (1, 0)
        return GeneratorOf {
            (b, a) = (a, b + a)
            if b > max { return nil }
            return b
        }
    }
}


let sum = reduce(fibonacciTo(4_000_000), 0) {a, n in (n % 2 == 0) ? a + n : a }

作为替代方案，如果您想保留fibonacci您可以扩展的更通用的功能SequenceOf with takeWhile and reduce1获得某物类似于功能组成：

 extension SequenceOf {
    func takeWhile(p: (T) -> Bool) -> SequenceOf<T> {
        return SequenceOf { _ -> GeneratorOf<T> in
            var generator = self.generate()
            return GeneratorOf {
                if let next = generator.next() {
                    return p(next) ? next : nil
                }
                return nil
            }
        }
    }

    // Reduce1 since name collision is not resolved
    func reduce1<U>(initial: U, combine: (U, T) -> U) -> U {
        return reduce(self, initial, combine)
    }
}


func fibonacci() -> SequenceOf<Int> {
    return SequenceOf { _ -> GeneratorOf<Int> in
        var (a, b) = (1, 0)
        return GeneratorOf {
            (b, a) = (a, b + a)
            return b
        }
    }
}

let sum2 = fibonacci()
    .takeWhile({ $0 < 4_000_000 })
    .reduce1(0) { a, n in (n % 2 == 0) ? a + n : a}

希望这可以帮助