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 ElementHere 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
Optionclass.
I’ve added this definition of reduce() to Iterable, and it will be available in the next release of Ceylon.
