After my previous post on finding minimums, a couple of people pointed out that reduce would be much better suited to the task. They’re absolutely right, but I ignored that for the last post since I had another agenda. Plus, the combination of min and reduce is an interesting one with its own wrinkles, that deserves a post of its own, so here it is.

reduce takes a sequence, a starting value, and a combining function, and uses that function to boil the sequence down to a single value. For example, to total up the values in an array:

let a = [2, 4, 6, 8]
// starting with 0, add each value
// of 'a' to a running total
let sum = reduce(a, 0, +)
// sum = 20

That certainly sounds like what we want for finding the minimum value in a sequence, with min as the combining function (as recently made possible in beta 3):

let a = [5, 4, 3, 8]
// but what to put in the starting value?
let the_min = reduce(a, ???, min)

We need to pick a starting value to use on the first call to min. Unlike with addition, there’s no natural constant to start a search for a minmum value. You could start with the maximum value for an Int, but that smells like a hack.

Using the first element of the sequence would do it:

var gen = a.generate()
if let first = gen.next() {
    reduce(a, first, min)
}

But this means the first thing this code does every time is redundantly compare the first element to itself. Strictly speaking, that’s fine from a functional behaviour point of view, and even the performance consequences amortize to negligible, but it’s not very satisfying.

This version avoids that problem:

var gen = a.generate()
if let first = gen.next() {
    reduce(gen, first, min)
}

Why does that work? Because Array.GeneratorType happens to be both a Generator and a Sequence. In fact, in a quick scan through the Swift standard library, I couldn’t spot any generator that wasn’t also a sequence. But just because they always are doesn’t mean they have to be, which is why implementing a generic function tail that returns all but the first element of a sequence is surprisingly tricky – but let’s leave that for a later post.

So, armed with our ability to use reduce to find a minimum, let’s implement our solution from the previous post that finds the minimum numeric value in an array of strings:

let string_ints = ["dog", "12", "cat", "4", "200", "elephant"]

var gen = string_ints.generate()
if let first = gen.next() {
    reduce(gen, first) { (lhs, rhs) in
        switch (lhs.toInt(), rhs.toInt()) {
        case (_, nil): return lhs
        case (nil, _): return rhs
        case (let i, let j): return i < j ? lhs : rhs
        }
    }
}

OK that works, but this is pretty ugly with the generator on top of that convoluted closure. And remember last time I mentioned there were still a couple of issues – if string_ints contains no integer strings, it’ll just return the first non-integer string. And it does every integer conversion twice.

Do we still need the generator? Our closure that chooses between sequence elements now discards nil values as soon as it finds a non-nil one. That means that we could supply nil as our initial argument. This also means a returned value of nil could stand in for “not found”, either because the sequence was empty, or because it contained no strings convertible to numbers.

But before we make that change, let’s neaten things up by pulling out the code that does the nil discrimination into its own function.

Here is combineMaybe, a function that takes a function that combines two values (like min), and returns a new function that chooses between two optionals, always preferring the non-nil one before resorting to the supplied function if neither value is nil:^{1 2}

func combineMaybe<T>
  ( combine: (T,T)->T ) 
  -> (T?,T?)->T? {
    return { lhs, rhs in
        switch(lhs, rhs) {
        case (_, nil): return lhs
        case (nil, _): return rhs
        default: return combine(lhs!,rhs!)
        }
    }
}

combineMaybe is a function decorator – a function that takes another function, and enhances it in some useful way, returning the enhanced function.

We can now use the standard library version of min, enhanced with our decorator, as the combiner function to reduce, supplying nil as the starting value. An initial call to map to first convert the strings to integers generates the input sequence:

let string_ints = ["dog", "12", "cat", "4", "200", "elephant"]
let maybe_ints = map(string_ints) { $0.toInt() }

if let the_min = reduce( maybe_ints, nil, combineMaybe(min)) {
    // the_min = 4
}
else {
    // handle both empty input or no numerics in input
}

This fixes the bug of returning a non-numeric string when that’s all the sequence contains. And it only converts each number once, in the call to map.^{3 4}

If instead we wanted to pull out the maximum values, all that is needed is to replace the passing of min into combineMaybe with max, with everything else remaining the same.

In fact, it’ll even work with other binary functions as well. If you replaced min with +, it’ll add all the numeric values in the array, while still giving you a chance to catch if no numbers were found in the sequence (sometimes zero is still not the right answer for an empty sequence, even one containing integers rather than strings).