MapReduce.Swift

public extension SequenceType {
  func reduce(@noescape combine: (Generator.Element, Generator.Element) -> Generator.Element) -> Generator.Element? {
    var g = self.generate()
    return g.next().map {
      (var accu) in
      while let next = g.next() { accu = combine(accu, next) }
      return accu
    }
  }
}

public struct ScanGen<G : GeneratorType, T> : GeneratorType {
  
  typealias Element = T
  private let combine: (T, G.Element) -> T
  private var initial: T
  private var g: G
  
  public mutating func next() -> Element? {
    return g.next().map{
      initial = combine(initial, $0)
      return initial
    }
  }
}

public struct Scan1Gen<G : GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  private let combine: (G.Element, G.Element) -> G.Element
  private var accu: G.Element?
  private var g: G
  
  public mutating func next() -> Element? {
    return g.next().map{
      element in
      accu = accu.map{ combine($0, element) } ?? element
      return accu!
    }
  }
}

public struct LazyScanSeq<S : SequenceType, T> : LazySequenceType {
  
  typealias Generator = ScanGen<S.Generator, T>
  private let seq: S
  private let combine: (T, S.Generator.Element) -> T
  private let initial: T
  
  public func generate() -> Generator {
    return ScanGen(combine: combine, initial: initial, g: seq.generate())
  }
}

public struct LazyScan1Seq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = Scan1Gen<S.Generator>
  private let seq: S
  private let combine: (S.Generator.Element, S.Generator.Element) -> S.Generator.Element
  
  public func generate() -> Generator {
    return Scan1Gen(combine: combine, accu: nil, g: seq.generate())
  }
}

public extension LazySequenceType {
  func scan<T>(initial: T, combine: (T, Generator.Element) -> T) -> LazyScanSeq<Self, T> {
    return LazyScanSeq(seq: self, combine: combine, initial: initial)
  }
  func scan(combine: (Generator.Element, Generator.Element) -> Generator.Element) -> LazyScan1Seq<Self> {
    return LazyScan1Seq(seq: self, combine: combine)
  }
}