Suma Fibonacciego używa Funkcjonalnego Swifta

Question

Próbuję nauczyć się funkcjonalnego Swifta i zacząłem wykonywać pewne ćwiczenia z Projektu Euler.

numery Nawet Fibonacciego Problem 2 Każdy nowy termin w ciągu Fibonacciego jest generowany przez dodanie dwóch poprzednich terminów. Rozpoczynając od dnia 1 i 2, pierwsze 10 terminy będą:

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

przy wzięciu pod uwagę warunki w sekwencja Fibonacciego, której wartości nie przekraczają czterech milionów, znajdź sumę wartości parzystych.

Wprowadzono memoized funkcji Fibonacciego według WWDC rozszerzone Swift wideo:

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

i realizowane klasy zgodnej z protokołem

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

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

Sequence Pierwszy (niefunkcjonalnych) rozwiązanie problemu:

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) 

Drugi, rozwiązanie bardziej funkcjonalne, używając ExSwift za to takeWhile funkcja

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

chciałbym poprawić to rozwiązanie, ze względu na zakres 1...40 Pod żebranie, który jest obliczających zbyt wielu kategoriach bez powodu. Idealnie chciałbym mieć jakiś nieskończony zakres, ale jednocześnie obliczać tylko wymagane warunki, które spełniają warunki w jakimkolwiek stanie sugestii?

Answer 1

Istnieje funkcja filter(), która przyjmuje sekwencję jako argument:

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

ale ponieważ wartość zwracana jest tablica, to nie nadaje się, jeśli chcesz pracować z „nieskończonej” sekwencji. Ale z

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

otrzymujesz "nieskończoną" sekwencję równych liczb Fibonacciego.Nie można wywołać metody w tej sekwencji, ponieważ .takeWhile() jest zdefiniowany tylko dla struct SequenceOf, a nie dla ogólnych sekwencji . Ale

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

prace i daje sekwencję wszystkich liczb parzystych Fibonacciego mniej niż 4.000.000. Następnie

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

daje zamierzony rezultat i oblicza tylko „konieczne” liczb Fibonacciego.

Należy zauważyć, że nie ma faktycznej potrzeby zapamiętania numerów Fibonacci tutaj, ponieważ są one dostępne sekwencyjnie. Również (jak już zauważyłem @Matteo ), wszystkie liczby Fibonacciego są liczbami całkowitymi. Więc można określić sekwencję prościej jako

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

i powyższe obliczenia ma nadal działać.

Answer 2

Tutaj generuję sekwencję, która zatrzymuje się już po osiągnięciu maksymalnej wartości. Następnie wystarczy zmniejszyć bez filtrowania, po prostu 0, gdy n jest nieparzysta.

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 } 

Jako alternatywa, jeśli chcesz zachować fibonacci bardziej ogólną funkcję można przedłużyć SequenceOf z takeWhile i reduce1 uzyskania czegoś, podobny skład funkcja:

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} 

Nadzieja to pomaga

Answer 3

Możesz zbliżyć się do tego, co chcesz, używając leniwych sekwencji Swift. Jeśli wziąć swój generator liczb Fibonacciego (tutaj jest jeden używam :)

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

var fibs = GeneratorOf<Int> { 

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

    return b 

} 

można zawinąć go w leniwe():

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

var fibs = lazy(

    GeneratorOf<Int> { 

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

    return b 

    } 
) 

co naraża go do filtrowania() jako leniwa funkcja. Ten filtr() zwraca:

LazySequence<FilterSequenceView<GeneratorOf<Int>>> 

Teraz, żeby dostać swoją funkcję takeWhile(), trzeba by przedłużyć 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 }}) 

    } 
} 

tak, że zwraca nil (zatrzymuje generator), czy też podstawowa sekwencja się kończy lub warunek nie jest spełniony.

Z wszystkich, że Twój ciąg Fibonacciego pod danym numerem wygląda trochę jak to, czego chciał:

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

//2, 8, 34 

Ale, ponieważ zmniejszenie nie jest metodą na LazySequence, trzeba konwertować do tablicy :

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

//44 

można zrobić szybki i brudny rozszerzenie LazySequence aby zmniejszyć():

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 

    } 
} 

I można napisać ostateczną rzeczą tak:

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

//44 

Wszystkie te sekwencje dostać się utrzymywać w ich lenistwo - bujda jest nieskończona, więc nie byłoby naprawdę działa inaczej. W rzeczywistości nic nie jest obliczane, zanim nie zredukujesz: do tego czasu wszystkie są słabe.

Answer 4

W Swift 3.1, oto iterator, który generuje liczb Fibonacciego na zawsze, a nieskończona sekwencja pochodzi od niego:

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

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

let fibs = AnySequence{FibIterator()} 

można uzyskać sumę parzystych warunkach, na czterech milionów tak:

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

Ostrzegamy, że filter i map są domyślnie surowe i będą działać wiecznie w nieskończonej sekwencji. W powyższym przykładzie nie ma to znaczenia, ponieważ prefix zwraca tylko skończoną liczbę wartości. Możesz zadzwonić pod numer .lazy, aby uzyskać leniwą sekwencję, w której filter i map zachowają się nieskończenie. Na przykład tutaj są pierwsze 5 parzystych liczb Fibonacciego:

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