Is it possible to cut short evaluation of a higher-level function?

Question

I am looking for a way to stop a higher-level function after evaluating part of its input sequence.

Consider a situation when you look for the first index in a sequence that satisfies a certain condition. For example, let's say we are looking for the first position in an array a of Ints where the sum of two consecutive values is above 100.

You can do it with a loop, like this:

func firstAbove100(a:[Int]) -> Int? {
    if a.count < 2 {
        return nil
    }
    for i in 0..<a.count-1 {
        if a[i]+a[i+1] > 100 {
            return i
        }
    }
    return nil
}

The looping stops as soon as the position of interest is discovered.

We can rewrite this code using reduce as follows:

func firstAbove100(a:[Int]) -> Int? {
    if a.count < 2 {
        return nil
    }
    return (0..<a.count-1).reduce(nil) { prev, i in
        prev ?? (a[i]+a[i+1] > 100 ? i : nil)
    }
}

However, the disadvantage of this approach is that reduce goes all the way up to a.count-2 even if it finds a match at the very first index. The result is going to be the same, but it would be nice to cut the unnecessary work.

Is there a way to make reduce stop trying further matches, or perhaps a different function that lets you stop after finding the first match?

Answer 1

As already said, reduce is specifically designed in order to evaluate an entire sequence and therefore not designed to short-circuit. Using it in this way to find an the index of an element that meets a given predicate is best done with indexOf as @Casey says.

Also as of Swift 3, there is now a first(where:) function on Sequence that allows you to find the first element that satisfies a given predicate. This could be an even more suitable alternative than indexOf, as it returns the element instead of the index (although in your particular example these are the same).

You could write your example like this:

func firstAbove100(_ a:[Int]) -> Int? {
    guard a.count > 1 else {return nil}

    return (0..<a.count-1).first { i in
        a[i]+a[i+1] > 100
    }
}

However if you want a more general high level function that will iterate through a sequence and break out if it finds a non-nil result of a given predicate – you could always write your own find function:

extension SequenceType {

    func find<T>(@noescape predicate: (Self.Generator.Element) throws -> T?) rethrows -> T? {
        for element in self {
            if let c = try predicate(element) {return c}
        }
        return nil
    }
}

You could now write your firstAbove100 function like this:

func firstAbove100(a:[Int]) -> Int? {
    if a.count < 2 {
        return nil
    }
    return (0..<a.count-1).find { i in
        a[i]+a[i+1] > 100 ? i : nil
    }
}

and it will now short-circuit when it finds a pair of elements that add to above 100.

Or let's say instead of returning the index of the first pair of elements in your array that add to greater than 100, you now want to return the sum of the elements. You could now write it like this:

func sumOfFirstAbove100(a:[Int]) -> Int? {
    guard a.count > 1 else {return nil}
    return (0..<a.count-1).find { i in
        let sum = a[i]+a[i+1]
        return sum > 100 ? sum : nil
    }
}

let a = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(sumOfFirstAbove100(a)) // prints: Optional(110)

The find function will iterate through the array, applying the predicate to each element (in this case the indices of your array). If the predicate returns nil, then it will carry on iterating. If the predicate returns non-nil, then it will return that result and stop iterating.

Answer 2

indexOf will stop after it finds the first match so you might rewrite firstAbove100 to something like this:

func firstAbove100(a:[Int]) -> Int? {
    return a.count > 1 ? (a.startIndex..<a.endIndex-1).indexOf({ a[$0] + a[$0 + 1] > 100 }) : nil
}