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 noninteger 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 nonnil
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 nonnil
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 nonnumeric 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).

The “maybe”based name comes from Haskell, where
maybe
is a function that takes a default value, a function, and an optional type (which are called Maybe types). ↩  As ever, really wishing switch was an expression that returned the value of its cases when they were single expressions. ↩
 Ok, so this doesn’t fulfil the original requirement of returning a string rather than an integer (from the previous article). I think we can keep that as a subsequent step, I was mostly being antagonistic about that part. ↩

Haskell also has a function,
mapMaybe
, that is like amap
to an optional value, followed by afilter
that removes all the resulting nil values. That would be a good building block for solving this problem too, though it still wouldn’t help with the starting value for reduce. ↩
> though it still wouldn’t help with the starting value for reduce.
For the problem with reduce requiring an initial value you could package your generator based approach (liked that!) into a new function reduce1 (similar to foldl1 or foldr1 in Haskell).
I had to wrap the generator into GeneratorOf(), though, because the generator of a sequence isn’t a Sequence itself:
/// reduce `sequence` using the function `combine`
func reduce1(sequence: S, combine: (E, E) > E) > E? {
var gen = sequence.generate()
if let first = gen.next() {
return reduce(GeneratorOf(gen), first, combine)
}
else {
return nil
}
}
Like “switch” “if” should really be an expression…
But we can use map instead for a more cons ice expression:
func reduce1(sequence: S, combine: (E, E) > E) > E? {
var gen = sequence.generate()
return gen.next().map { first in reduce(GeneratorOf(gen), first, combine) }
}
I chose handling the empty sequence case with an optional return type instead of requiring a non empty sequence argument like Haskell’s foldl1 does (don’t know why they didn’t choose to use Maybe).
Thorsten