A better way to hit bottom

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


  1. 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). 
  2. As ever, really wishing switch was an expression that returned the value of its cases when they were single expressions. 
  3. 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. 
  4. Haskell also has a function, mapMaybe, that is like a map to an optional value, followed by a filter 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. 

One thought on “A better way to hit bottom

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s