RecSeq.Swift

struct LayerGen<T> : GeneratorType {
  
  typealias Element = T
  private let proc: T -> T
  
  private var prev: T
  
  mutating func next() -> Element? {
    prev = proc(prev)
    return prev
  }
}

struct LayerSeq<T> : LazySequenceType {
  
  typealias Generator = LayerGen<T>
  
  private let start: T
  private let proc: T -> T
  
  func generate() -> Generator {
    return LayerGen(proc: proc, prev: start)
  }
}

struct RecGenMEM<T> : GeneratorType {
  
  typealias Element = T
  private var prevs: [T?]
  private let recFunc: ((Int -> T), Int) -> T
  
  private var i: Int
  
  private mutating func f(i: Int) -> T {
    if i == prevs.count {
      prevs.append(Optional<T>())
    } else if i > prevs.count {
      prevs.extend(Repeat(count: (i + 1 - prevs.count), repeatedValue: Optional<T>()))
    }
    if let r = prevs[i] {
      return r
    } else {
      let r = recFunc(f, i)
      prevs[i] = r
      return r
    }
  }
  mutating func next() -> Element? { return f(++i) }
}

struct RecSeqMEM<T> : LazySequenceType {
  
  typealias Generator = RecGenMEM<T>
  
  private let base: [T?]
  private let recFunc: ((Int -> T), Int) -> T
  
  func generate() -> Generator {
    return RecGenMEM(prevs: base, recFunc: recFunc, i: -1)
  }
  
  init(_ base: [T], recFunc: ((Int -> T), Int) -> T) {
    self.recFunc = recFunc
    self.base = base.map{Optional($0)}
  }
  
  init(_ base: T, recFunc: ((Int -> T), Int) -> T) {
    self.recFunc = recFunc
    self.base = [Optional(base)]
  }
}

func memoize<A : Hashable, T>(var base: [A:T], recFunc: ((A -> T), A) -> T) -> (A -> T) {
  func f(n: A) -> T {
    if let r = base[n] { return r }
    let r = recFunc(f, n)
    base[n] = r
    return r
  }
  return f
}

struct RecGenTCO<T> : GeneratorType {
  
  typealias Element = T
  private var prevs: [T]
  private let recFunc: ((Int -> T), Int) -> T
  
  private var i: Int
  
  private mutating func f(i: Int) -> T {
    return i < prevs.count ? prevs[i] : recFunc(f, i)
  }
  mutating func next() -> Element? {
    if ++i == prevs.count { prevs.append(f(i)) }
    return prevs[i]
  }
}

struct RecSeqTCO<T> : LazySequenceType {
  
  typealias Generator = RecGenTCO<T>
  
  private let base: [T]
  private let recFunc: ((Int -> T), Int) -> T
  
  func generate() -> Generator {
    return RecGenTCO(prevs: base, recFunc: recFunc, i: -1)
  }
  
  init(_ base: [T], recFunc: ((Int -> T), Int) -> T) {
    self.recFunc = recFunc
    self.base = base
  }
  
  init(_ base: T, recFunc: ((Int -> T), Int) -> T) {
    self.recFunc = recFunc
    self.base = [(base)]
  }
}