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.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

Leave a Reply


three + 6 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
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.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close