Skip to content

Latest commit

 

History

History
108 lines (80 loc) · 5.31 KB

0094-sequence-function.md

File metadata and controls

108 lines (80 loc) · 5.31 KB
Raw

Add sequence(first:next:) and sequence(state:next:) to the stdlib

Introduction

This proposal introduces sequence(first:next:) and sequence(state:next:), a pair of global functions that return (potentially-infinite) sequences of lazy applications of a closure to an initial value or a mutable state.

Swift-evolution thread:

Discussion thread topic for SE-0045

Initial Discussion

Motivation

SE-0045, originally proposed iterate(_:apply:) (see SE-0045r1), a method that was subsequently changed to unfold(_:applying:). The proposal was accepted with modifications. The core team rejected unfold based on its naming. As its core utility remains unquestionably high, this proposal re-introduces the method with better, more Swift-appropriate naming.

This function provides the natural counterpart to reduce as well as a replacement for non-striding C-style for loops that were removed by the acceptance of SE-0007, sequence can be used to apply generation steps that use non-linear math or apply non-mathematical operations, as in the following examples:

for x in sequence(first: 0.1, next: { $0 * 2 }).prefix(while: { $0 < 4 }) {
    // 0.1, 0.2, 0.4, 0.8, ...
}

and

for view in sequence(first: someView, next: { $0.superview }) {
    // someView, someView.superview, someView.superview.superview, ...
}

See also:

Detailed design

The declarations for the proposed functions look like:

public func sequence<T>(first: T, next: T -> T?) -> UnfoldSequence<T>
public func sequence<T, State>(state: State, next: (inout State) -> T?) -> UnfoldSequence<T>

Both functions return potentially-infinite sequences of lazy repeated applications of a function to an initial value or a state.

The first function, sequence(first:next:), yields the first value, followed by a series of values derived from invoking next using the previous value. The yielded sequence looks like [first, next(first), next(next(first)), ... . This sequence terminates when the next function returns nil. If the function never returns nil the sequence is infinite. This function is equivalent to Haskell's iterate, however the Swift version is not always infinite and may terminate.

The second function, sequence(state:next:), passes the state value as an inout parameter to next and yields each subsequent return value. This function is equivalent to Haskell's unfoldr, though we've chosen to make the state an inout parameter instead of returning a new state as this is less likely to produce unwanted Copy on Write (COW) copies of data structures.

Both functions return a sequence type named UnfoldSequence. Existing Swift naming conventions would call this SequenceSequence. Using UnfoldSequence instead resolves the unwarranted redundancy and provides a meaningful reference to developers familiar with functional programming languages.

Impact on existing code

None, this change is purely additive.

Alternatives considered

The natural name for sequence(state:next:) is unfold. Functional languages that offer unfold pair it with fold, which has already been established in Swift as reduce. Renaming reduce has already been rejected. The name sequence best describes this function in Swift. unfold on its own is not descriptive and has no meaning to developers not familiar with functional programming languages.

The function sequence(first:next:) can be expressed using sequence(state:next:). We include it in this proposal due to this form's high utility. Correctly reimplementing this form in terms of sequence(state:next:) is non-trivial; the simple solution is more eager than it should be.