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.
 

Reference: The signature of reduce() in Ceylon from our JCG partner Gavin King at the Ceylon Team blog blog.
Related Whitepaper:

Java Essential Training

Author David Gassner explores Java SE (Standard Edition), the language used to build mobile apps for Android devices, enterprise server applications, and more!

The course demonstrates how to install both Java and the Eclipse IDE and dives into the particulars of programming. The course also explains the fundamentals of Java, from creating simple variables, assigning values, and declaring methods to working with strings, arrays, and subclasses; reading and writing to text files; and implementing object oriented programming concepts. Exercise files are included with the course.

Get it Now!  

Leave a Reply


two + 6 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

15,153 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books