Sum of Fibonacci term using Functional Swift

Question

I'm trying to learn functional Swift and started doing some exercises from Project Euler.

Even Fibonacci numbers Problem 2 Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Implemented a memoized Fibonacci function, as per WWDC advanced Swift videos:

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

and implemented a class that conforms to the Sequence protocol

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

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

The first (non-functional) solution of the problem:

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)

The second, more functional solution, using ExSwift for it's takeWhile function

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

I'd like to improve on this solution, because of the 1...40 range at the begging that's calculating too many terms for no reason. Ideally I'd like to be able to have some sort of infinite range, but at the same time only calculate the required terms that satisfy the condition in the takeWhile

Any suggestions ?

Answer 1

Here I generate the sequence that already stops once max value is reached. Then you just need to reduce without filtering, just sum 0 when 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 }

As an alternative, if you wish to keep fibonacci a more general function you could extend SequenceOf with takeWhile and reduce1 obtaining something that resembles function composition:

 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}

Hope this helps