# The signature of reduce() in Ceylon

The `Iterable`

interface defines a method named `fold()`

with
this signature:

```
Result fold<Result>(Result initial,
Result accumulating(Result partial, Element elem))
```

Where `Element`

is the element type of the `Iterable`

. This
method accepts an initial value, and an accumulator function
which is applied to each element of the iterable object in
turn. For example:

```
Integer sum = (1..10).fold(0, plus<Integer>);
```

Sometimes, we don't need the initial value, since can simply
start accumulating from the first element. Following the
convention used by Scala and F#, let's call this function
`reduce()`

. Then we would like to be able to write:

```
Integer sum = (1..10).reduce(plus<Integer>);
```

But what should the signature of this method be? A first stab might give us:

```
Element reduce(Element accumulating(Element partial, Element elem))
```

But this signature is a bit more restrictive than it should
be. It's perfectly reasonable for the result type of `reduce()`

to be a supertype of the element type. Scala handles this using
a lower bound type constraint. Transliterating this to Ceylon,
using an imaginary syntax for lower bounds, it would look like:

```
Result reduce<Result>(Result accumulating(Result partial, Element elem))
given Result abstracts Element
```

Here the lower bound constraint ensures that the first element is assignable to the first parameter of the accumulator function.

But Ceylon doesn't have lower bound type constraints. Why? Well, because it seems that we can in practice almost always use union types to achieve the same effect. So let's try that:

```
Result|Element reduce<Result>(
Result accumulating(Result|Element partial, Element elem))
```

Now let's try to implement this signature. One possibility would be:

```
Result|Element reduce<Result>(
Result accumulating(Result|Element partial, Element elem)) {
assert (!empty, is Element initial = first);
variable Result|Element partial = initial;
for (elem in rest) {
partial = accumulating(partial, elem);
}
return partial;
}
```

The assertion handles the case of an empty `Iterable`

, resulting
in an `AssertionException`

if the iterable object has no first
element.

Alternatively, we might prefer to return `null`

in the case of
an empty `Iterable`

, which suggests the following implementation:

```
Result|Element|Null reduce<Result>(
Result accumulating(Result|Element partial, Element elem)) {
if (!empty, is Element initial = first) {
variable Result|Element partial = initial;
for (elem in rest) {
partial = accumulating(partial, elem);
}
return partial;
}
else {
return null;
}
}
```

Going back to Scala, we notice that Scala has two versions of
`reduce()`

, which are exactly analogous to the two possibilities
we've just seen. The first version throws an exception in the
empty case, and the second version, `reduceOption()`

, returns an
instance of the wrapper class `Option`

.

But in Ceylon, we can do better. In Ceylon, `Iterable`

has a
slightly mysterious-looking second type parameter, named `Absent`

,
with an upper bound `given Absent satisfies Null`

. An
`Iterable<T,Null>`

, which we usually write `{T*}`

, is a
*possibly-empty* iterable. An `Iterable<T,Nothing>`

, which we
usually write `{T+}`

, is an iterable we know to be nonempty.

Thus we arrive at the following definition of `reduce()`

:

```
Result|Element|Absent reduce<Result>(
Result accumulating(Result|Element partial, Element elem)) {
value initial = first;
if (!empty, is Element initial) {
variable Result|Element partial = initial;
for (elem in rest) {
partial = accumulating(partial, elem);
}
return partial;
}
else {
return initial;
}
}
```

Now, for a "spanned" range expression like `1..n`

, which is
nonempty, we get a non-null return type:

```
Integer sum = (1..n).reduce(plus<Integer>);
```

On the other hand, for a "segmented" range expression like
`1:n`

, which is possibly-empty, we get an optional return
type:

```
Integer? sum = (1:n).reduce(plus<Integer>);
```

Best of all, it never throws an exception. This is, I humbly submit, Pretty Damn Nice.

Notice just how much work union types are doing for us here.
Compared to Scala's `reduce()`

/`reduceOption()`

, they let us
eliminate:

- a lower bound type constraint,
- a second, effectively overloaded, version of the method, and
- the wrapper
`Option`

class.

I've added this definition of `reduce()`

to `Iterable`

, and
it will be available in the next release of Ceylon.