Suggested replacement for C-style for.

Example.swift

// Sequence of 1, 2, 4 ... 64
induce(from: 1, to: 128, by: { $0 * 2 })
induce(from: 1, to: 128, by: { $0 *= 2 })

// Sequence of 1, 2, 4 ... 128
induce(from: 1, through: 128, by: { $0 * 2 })
induce(from: 1, through: 128, by: { $0 *= 2 })

// Sequence of 1, 2, 4 ... with arbitrary, calculated bound
import Darwin
induce(from: 1, while: { sqrt(Double($0)) < 20 }, by: { $0 * 2 })
induce(from: 1, while: { sqrt(Double($0)) < 20 }, by: { $0 *= 2 })

// Sequence of two values in a tuple:
induce(from: (1, 10), while: { $0.0 < 128 }, by: { $0.0 *= 2; $0.1 *= 2 })

// C-style for loop:
for var i = 1; i < 128; i *= 2 { print(i) }
// Literal converted form:
for i in induce(from: 1, while: { $0 < 128 }, by: { $0 *= 2 }) { print(i) }
// Idomatic converted form:
for i in induce(from: 1, to: 128, by: { $0 * 2 }) { print(i) }

// It would be really nice if you could say something like one of these:
//     for i in induce(from: 1, to: 128, by: * 2) { print(i) }
//     for i in induce(from: 1, to: 128, by: _ * 2) { print(i) }
//     for i in induce(from: 1, to: 128, by: i * 2) { print(i) }
// But that kind of thing has been rejected before. Sigh...

Induce.swift

// This file is not optimized or stdlib-ready. It's merely meant to demonstrate the logic the various 
// `induce` functions are intended to implement.

/// Returns a lazy sequence which begins with the `start` element, then derives subsequent elements 
/// by repeatedly calling the `next` function with the previous element to calculate the next element. 
/// Continues as long as the `inBounds` function continues to return `true` for each element.
/// 
/// If `inBounds` is omitted, the sequence created by this function is infinite. 
public func induce<Element>(from start: Element, while inBounds: Element -> Bool = { _ in true }, by next: Element -> Element) -> InductionSequence<Element> {
    return induce(from: start, while: inBounds, by: formify(next))
}

/// Returns a lazy sequence which begins with the `start` element, then derives subsequent elements 
/// by repeatedly calling the `formNext` function to transform the previous element into the next one.
/// Continues as long as the `inBounds` function continues to return `true` for each element.
/// 
/// If `inBounds` is omitted, the sequence created by this function is infinite.
public func induce<Element>(from start: Element, while inBounds: Element -> Bool = { _ in true }, by formNext: inout Element -> Void) -> InductionSequence<Element> {
    return InductionSequence(start: start, inBounds: inBounds, formNext: formNext)
}

/// Returns a lazy sequence which begins with the `start` element, then derives subsequent elements 
/// by repeatedly calling the `next` function with the previous element to calculate the next element.
/// Continues as long as the elements stay between `start` (inclusive) and `end` (exclusive).
func induce<Element: Comparable>(from start: Element, to end: Element, by next: Element -> Element) -> InductionSequence<Element> {
    return induce(from: start, to: end, by: formify(next))
}

/// Returns a lazy sequence which begins with the `start` element, then derives subsequent elements 
/// by repeatedly calling the `formNext` function to transform the previous element into the next one.
/// Continues as long as the elements stay between `start` (inclusive) and `end` (exclusive).
func induce<Element: Comparable>(from start: Element, to end: Element, by formNext: inout Element -> Void) -> InductionSequence<Element> {
    let inBounds = (start < end) ? { $0 < end } : { $0 > end }
    return induce(from: start, while: inBounds, by: formNext)
}

/// Returns a lazy sequence which begins with the `start` element, then derives subsequent elements 
/// by repeatedly calling the `next` function with the previous element to calculate the next element.
/// Continues as long as the elements stay between `start` (inclusive) and `end` (inclusive).
func induce<Element: Comparable>(from start: Element, through end: Element, by next: Element -> Element) -> InductionSequence<Element> {
    return induce(from: start, through: end, by: formify(next))
}

/// Returns a lazy sequence which begins with the `start` element, then derives subsequent elements 
/// by repeatedly calling the `formNext` function to transform the previous element into the next one.
/// Continues as long as the elements stay between `start` (inclusive) and `end` (inclusive).
func induce<Element: Comparable>(from start: Element, through end: Element, by formNext: inout Element -> Void) -> InductionSequence<Element> {
    let inBounds = (start < end) ? { $0 <= end } : { $0 >= end }
    return induce(from: start, while: inBounds, by: formNext)
}

/// A lazy, possibly infinite sequence derived from a starting element and a function which calculates 
/// the next value.
/// 
/// -SeeAlso: `induce(from:to:by:)`, `induce(from:through:by:)`, `induce(from:while:by:)`
public struct InductionSequence<Element>: SequenceType {
    let start: Element
    let inBounds: Element -> Bool
    let formNext: inout Element -> Void
    
    public func generate() -> InductionGenerator<Element> {
        return .init(current: start, inBounds: inBounds, formNext: formNext)
    }
}

/// A lazy, possibly infinite generator associated with an `InductionSequence`.
public struct InductionGenerator<Element>: GeneratorType {
    var current: Element
    let inBounds: Element -> Bool
    let formNext: inout Element -> Void
    
    public mutating func next() -> Element? {
        if !inBounds(current) {
            return nil
        }
        defer { formNext(&current) }
        return current
    }
}

/// Converts a functional-style operation into a mutating-style operation.
private func formify<T>(function: T -> T) -> (inout T) -> Void {
    return { $0 = function($0) }
}

@therealbnut formNext(_:) has to be called after the current value is fetched. The alternative is to do something like this:

let ret = current
formNext(&current)
return ret

Using defer seemed simpler.

Could you have?

induce(1...128, by: { $0 * 2 })

Or:

(1...128).induce(by: { $0 * 2 })

@brentdax ah right, sorry I missed the &.

@BurntCaramel it would be a nice convenience, but it's not as flexible; it only works on things that can be represented by a range, and it doesn't work as well with values counting down.

I think this is an algorithm commonly known as “scan”.

@dabrahams I'm not sure if you got it right: scan is the operation that takes a sequence xs: [T], an initial value y: U, and a function f: (U, T) -> U, and returns the sequence

xs.scan(y, combine: f) == [
          y,
        f(y, xs[0]),
      f(f(y, xs[0]), xs[1]),
    f(f(f(y, xs[0]), xs[1]), xs[2]),
    ...,
    xs.reduce(y, combine: f)
]

So it's a close friend of reduce. (You could alternatively specify the resulting sequence to omit the initial prefix y, making xs.scan(y, combine: f) of equal length with xs.)

@brentdax I'd think implementing Clojure's iterate in Swift might be a good idea:

struct LazyIterateSequence<T> : SequenceType { ... }

func iterate<T>(initial: T, step: T -> T) -> LazyIterateSequence<T> { ... }

It returns the "infinite" sequence (well, besides crashing on checked overflow) of x, f(x), f(f(x)), ..., which you'd implement with a lazy sequence structure. You would take what you need by using .prefix(n) or @kballard's proposed .takeWhile(pred):

// Sequence of 10 first powers of 2:
let xs = iterate(1) { $0 * 2 }.prefix(10)

// Sequence of powers of 2 less than 1000000:
let ys = iterate(1) { $0 * 2 }.takeWhile { $0 < 1000000 }

@BurntCaramel Sort of, yes. There are a couple of issues with it: it doesn't support the more flexible while: variant, and the "walk from end to start based on the sign of by:" trick doesn't work with a by: function. There are ways to make it work, but they're a little more painful. I would probably provide these variants:

induce(from: 1, while: { $0 < 128 }, by: { $0 * 2 })
induce(over: 1..<128, from: 1, by: { $0 * 2 })
induce(over: 1..<128, from: .start, by: { $0 * 2 })    // chooses the start of the range
induce(over: 1..<128, by: { $0 * 2 })                // uses from: .start if nothing else is specified

@pyrtsa takeWhile would obviate the need for while:. I didn't use it here for three reasons:

1. It's not in the standard library yet.
2. The pattern of induce(from: expr, while: function, by: function) closely matches the C-style for loop, and I thought a direct translation might be valuable.
3. I like the functionality of takeWhile, but not the name.

Even if we do have a takeWhile, though, I think we would want from:to/through: or an equivalent range-based version. The ability to declare the boundary values of an iteration instead of specifying a cutoff function is a win over C-style for, and I would like to make that available to users even when the by: is not something that stride can do.

@brentdax Heh, likewise, I like the functionality of induce but not the name. You could even call it iterate, and simply make the while:-less overload work the way I suggested.

1. True.
2. That's an interesting point. I'm not sure if it's that indirect if merely the order of arguments changes in the expression.
3. Naming is hard. I think some alternatives were discussed: xs.prefix {...} or even xs.while {...} could work as well.