Instantly share code, notes, and snippets.

# brentdax/Example.swift Last active Apr 7, 2016

Suggested replacement for C-style for.
 // 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...
 // 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(from start: Element, while inBounds: Element -> Bool = { _ in true }, by next: Element -> Element) -> InductionSequence { 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(from start: Element, while inBounds: Element -> Bool = { _ in true }, by formNext: inout Element -> Void) -> InductionSequence { 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(from start: Element, to end: Element, by next: Element -> Element) -> InductionSequence { 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(from start: Element, to end: Element, by formNext: inout Element -> Void) -> InductionSequence { 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(from start: Element, through end: Element, by next: Element -> Element) -> InductionSequence { 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(from start: Element, through end: Element, by formNext: inout Element -> Void) -> InductionSequence { 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: SequenceType { let start: Element let inBounds: Element -> Bool let formNext: inout Element -> Void public func generate() -> InductionGenerator { return .init(current: start, inBounds: inBounds, formNext: formNext) } } /// A lazy, possibly infinite generator associated with an `InductionSequence`. public struct InductionGenerator: 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(¤t) } return current } } /// Converts a functional-style operation into a mutating-style operation. private func formify(function: T -> T) -> (inout T) -> Void { return { \$0 = function(\$0) } }

### therealbnut commented Apr 5, 2016

 Is the `defer` on `46` needed?
Owner Author

### brentdax commented Apr 6, 2016

 @therealbnut `formNext(_:)` has to be called after the current value is fetched. The alternative is to do something like this: ``````let ret = current formNext(¤t) return ret `````` Using `defer` seemed simpler.

### BurntCaramel commented Apr 6, 2016

 Could you have? `induce(1...128, by: { \$0 * 2 })` Or: `(1...128).induce(by: { \$0 * 2 })`

### therealbnut commented Apr 6, 2016

 @brentdax ah right, sorry I missed the `&`.

### therealbnut commented Apr 6, 2016

 @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.

### dabrahams commented Apr 6, 2016

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

### pyrtsa commented Apr 7, 2016

 @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 : SequenceType { ... } func iterate(initial: T, step: T -> T) -> LazyIterateSequence { ... }``` 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 }```
Owner Author

### brentdax commented Apr 7, 2016

 @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: It's not in the standard library yet. 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. 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.

### pyrtsa commented Apr 7, 2016

 @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. True. That's an interesting point. I'm not sure if it's that indirect if merely the order of arguments changes in the expression. Naming is hard. I think some alternatives were discussed: `xs.prefix {...}` or even `xs.while {...}` could work as well.