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

Answer 2

There is a filter() function which takes a sequence as an argument:

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

but since the return value is an array, this is not suited if you want to work with an "infinite" sequence. But with

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

you get an "infinite" sequence of the even Fibonacci numbers. You cannot call the .takeWhile() method of ExSwift on that sequence because .takeWhile() is only defined for struct SequenceOf and not for general sequences. But

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

works and gives the sequence of all even Fibonacci numbers less than 4,000,000. Then

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

gives the intended result and computes only the "necessary" Fibonacci numbers.

Note that there is no actual need to memoize the Fibonacci numbers here because they are accessed sequentially. Also (as @Matteo already noticed), all Fibonacci numbers are integers. So you could define the sequence more simply as

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

and the above computation does still work.

Answer 3

You can get quite close to what you want by using Swift's lazy sequences. If you take your generator of fibonacci numbers (here's the one I'm using:)

var (a, b) = (1, 0)

var fibs =  GeneratorOf<Int> {

  (b, a) = (a, b + a)

  return b

}

You can wrap it in lazy():

var (a, b) = (1, 0)

var fibs = lazy(

  GeneratorOf<Int> {

    (b, a) = (a, b + a)

    return b

  }
)

Which exposes it to filter() as a lazy function. This filter() returns:

LazySequence<FilterSequenceView<GeneratorOf<Int>>>

Now, to get your takeWhile() function, you'd need to extend LazySequence:

extension LazySequence {

  func takeWhile(condition: S.Generator.Element -> Bool)
    -> LazySequence<GeneratorOf<S.Generator.Element>> {

    var gen = self.generate()

    return lazy( GeneratorOf{ gen.next().flatMap{ condition($0) ? $0 : nil }})

  }
}

So that it returns nil (stops the generator) if either the underlying sequence ends, or the condition isn't satisfied.

With all of that, your fibonacci sequence under a given number looks a lot like what you wanted:

fibs
  .filter {$0 % 2 == 0}
  .takeWhile {$0 < 100}

//2, 8, 34

But, because reduce isn't a method on LazySequence, you have to convert to an array:

fibs
  .filter {$0 % 2 == 0}
  .takeWhile {$0 < 100}.array
  .reduce(0, combine: +)

//44

You could do a quick and dirty extension to LazySequence to get reduce():

extension LazySequence {

  func reduce<U>(initial: U, combine: (U, S.Generator.Element) -> U) -> U {

    var accu = initial

    for element in self { accu = combine(accu, element) }

    return accu

  }
}

And you can write the final thing like this:

fibs
  .filter {$0 % 2 == 0}
  .takeWhile {$0 < 100}
  .reduce(0, combine: +)

//44

All of those sequences get to persist in their laziness - fibs is infinite, so they wouldn't really work otherwise. In fact, nothing is calculated until reduce: it's all thunks until then.

Answer 4

In Swift 3.1, here's an iterator that generates Fibonacci numbers forever, and an infinite sequence derived from it:

class FibIterator : IteratorProtocol {
    var (a, b) = (0, 1)

    func next() -> Int? {
        (a, b) = (b, a + b)
        return a
    }
}

let fibs = AnySequence{FibIterator()}

You can get the sum of the even-numbered terms under four million like this:

fibs.prefix{$0 < 4000000}.filter{$0 % 2 == 0}.reduce(0){$0 + $1}

Be warned that filter and map are strict by default, and will run forever on an infinite Sequence. In the example above, this doesn't matter since prefix returns only a finite number of values. You can call .lazy to get a lazy Sequence where filter and map will behave non-strictly. For example, here are the first 5 even Fibonacci numbers:

> print( Array(fibs.lazy.filter{$0 % 2 == 0}.prefix(5)) )
[2, 8, 34, 144, 610]