cartProd.swift

func cons<S : SequenceType>(h: S.Generator.Element)(s: S) -> [S.Generator.Element] {
  return [h] + s
}

private extension GeneratorType where Element : CollectionType {
  mutating private func product() -> [[Element.Generator.Element]] {
    return next()?.lazy.map(cons).flatMap(product().lazy.map) ?? [[]]
  }
}

extension SequenceType where Generator.Element : CollectionType {
  func product() -> [[Generator.Element.Generator.Element]] {
    var g = generate()
    return g.product()
  }
}

[[1, 2], [3, 4]].product() // [[1, 3], [1, 4], [2, 3], [2, 4]]