Somma del termine Fibonacci usando Functional Swift

Question

Sto cercando di imparare il funzionale Swift e ho iniziato a fare alcuni esercizi da Project Euler.

numeri Anche Fibonacci Problema 2 Ogni nuovo termine della sequenza di Fibonacci è generato sommando i precedenti due termini. Partendo da 1 e 2, i primi 10 termini saranno:

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

Considerando i termini la sequenza di Fibonacci i cui valori non superano i quattro milioni, trova la somma dei termini con valore pari.

implementato una funzione di Fibonacci memoized, come da WWDC avanzata video 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) } 

e implementato una classe che è conforme alla Sequence protocollo

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

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

La prima (non funzionale) soluzione del problema:

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) 

La seconda soluzione, più funzionale, utilizzando ExSwift per la sua takeWhile funzione

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

Mi piacerebbe migliorare su questa soluzione, a causa della gamma 1...40 ai accattonaggio che è calcolo troppi termini per nessun motivo. Idealmente mi piacerebbe poter avere una sorta di raggio infinito, ma allo stesso tempo calcolare solo i termini richiesti che soddisfano la condizione nello takeWhile

Qualche suggerimento?

Answer 1

C'è una funzione filter() che accetta una sequenza come argomento:

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

ma dal momento che il valore di ritorno è un serie, questo non è adatto se si vuole a lavorare con una sequenza "infinita". Ma con

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

si ottiene una sequenza "infinita" di numeri pari di Fibonacci.Non è possibile chiamare il metodo .takeWhile() di ExSwift in quella sequenza poiché .takeWhile() è definito solo per struct SequenceOf e non per le sequenze generali . Ma

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

opere e dà la sequenza di tutti i numeri di Fibonacci in meno rispetto 4.000.000. Poi

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

dà il risultato previsto e calcola solo le numeri di Fibonacci "necessari".

Nota che non è necessario registrare i numeri di Fibonacci qui perché sono accessibili in sequenza. Inoltre (come @Matteo già notato), tutti i numeri di Fibonacci sono numeri interi. Così si potrebbe definire la sequenza più semplicemente come

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

e quanto sopra calcolo fa ancora lavorare.

Answer 2

Qui viene generata la sequenza che si arresta una volta raggiunto il valore massimo. Quindi basta ridurre senza filtrare, basta sommare 0 quando n è dispari.

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 } 

In alternativa, se si desidera mantenere fibonacci una funzione più generale si potrebbe estendere SequenceOf con takeWhile e reduce1 ottenere qualcosa che assomiglia funzione di composizione:

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} 

Spero che questo aiuti

Answer 3

È possibile avvicinarsi a ciò che si desidera utilizzando le pigre sequenze di Swift. Se si prende il generatore di numeri di Fibonacci (qui è quella che sto usando :)

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

var fibs = GeneratorOf<Int> { 

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

    return b 

} 

È possibile avvolgere in pigro():

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

var fibs = lazy(

    GeneratorOf<Int> { 

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

    return b 

    } 
) 

che lo espone al filtro() come un funzione pigra. Questo filtro() restituisce:

LazySequence<FilterSequenceView<GeneratorOf<Int>>> 

Ora, per ottenere la funzione TakeWhile(), avresti bisogno di estendere 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 }}) 

    } 
} 

in modo che restituisca nil (arresta il generatore) se uno la sequenza sottostante termina o la condizione non è soddisfatta.

Con tutto ciò, la sequenza di Fibonacci con un dato numero assomiglia molto a quello che si voleva:

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

//2, 8, 34 

Ma, a causa di ridurre non è un metodo su LazySequence, è necessario convertire in un array :

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

//44 

Si potrebbe fare un'estensione rapido e sporco per LazySequence per ottenere ridurre():

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 

    } 
} 

e si può scrivere l'ultima cosa in questo modo:

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

//44 

Tutte queste sequenze arrivare a persistere nella loro pigrizia - FIBS è infinito, in modo che non sarebbe davvero lavorare diversamente. In realtà, nulla viene calcolato fino a ridurlo: sono tutti i thunks fino ad allora.

Answer 4

In Swift 3.1, ecco un iteratore che genera numeri di Fibonacci per sempre, e una sequenza infinita che ne derivano:

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

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

let fibs = AnySequence{FibIterator()} 

È possibile ottenere la somma dei termini di numero pari in quattro milioni di simile a questo:

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

Tieni presente che filter e map sono rigorosi per impostazione predefinita e verranno eseguiti per sempre su una sequenza infinita. Nell'esempio sopra, ciò non ha importanza dal momento che prefix restituisce solo un numero finito di valori. È possibile chiamare .lazy per ottenere una sequenza lenta in cui filter e map si comporteranno in modo non rigoroso. Ad esempio, ecco i primi 5 numeri di Fibonacci:

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