使用Functional Swift的Fibonacci项的和

Question

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

甚至Fibonacci数问题2 Fibonacci序列中的每个新项都是通过添加前两个项生成的.从1和2开始,前10个术语将是:

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

通过考虑Fibonacci序列中的值不超过四百万的项,找到偶数项的总和.

根据WWDC高级Swift视频实现了一个memoized斐波那契函数:

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

有什么建议 ？

Answer 1

有一个filter()函数将序列作为参数：

func filter<S : SequenceType>(source: S, includeElement: (S.Generator.Element) -> Bool) -> [S.Generator.Element]

但由于返回值是一个数组，如果您想使用“无限”序列，则这不适合。但与

lazy(FibonacciSequence()).filter ( { $0 % 2 == 0 })

您会得到偶数斐波那契数的“无限”序列。您不能在该序列上调用.takeWhile()ExSwift 的方法，因为 .takeWhile()仅为通用序列定义struct SequenceOf，而不是为通用序列定义。但

TakeWhileSequence(
    lazy(FibonacciSequence()).filter ( { $0 % 2 == 0 }),
    { $0 < 4_000_000 }
)

工作并给出所有小于 4,000,000 的偶数斐波那契数的序列。然后

let sum = reduce(TakeWhileSequence(
    lazy(FibonacciSequence()).filter ( { $0 % 2 == 0 }),
    { $0 < 4_000_000 }), 0, +)

给出预期结果并仅计算“必要的”斐波那契数。

请注意，这里实际上不需要记住斐波那契数，因为它们是按顺序访问的。另外（正如 @Matteo 已经注意到的那样），所有斐波那契数都是整数。所以你可以更简单地将序列定义为

struct FibonacciSequence : SequenceType {

    func generate() -> GeneratorOf<Int> {
        var current = 1
        var next = 1
        return GeneratorOf<Int>() {
            let result = current
            current = next
            next += result
            return result
        };
    }
}

并且上面的计算仍然有效。