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.

**The signature of reduce() in Ceylon from our JCG partner Gavin King at the Ceylon Team blog blog.**

*Reference:*
## Leave a Reply

Be the First to Comment!