# 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