Implementing ranges of fractions in Scala

Photo by timothy muza on Unsplash

A couple of months ago, I wrote about using JUnit from the command line to write a Fraction class in Scala using test-driven development (TDD). I left some stuff out, and the article was still more than 4,000 words (an 18-minute read, by Medium’s measurement).

The biggest thing I left out that I wanted to write about was implementing to() and by() for Fraction like there is to() and by() for Int in the standard Scala library.

Explaining what to() and by() do for Int would have really sidetracked me from JUnit, which, after all, was the main topic of my previous article. So I’m writing a separate article about it now, this article.

More often than you realize, you need a list of consecutive integers. For example, for the infamous FizzBuzz exercise, you need a list of the integers from 1 to 100.

In most procedural and object-oriented programming languages, you’d probably have to write a for loop and add the numbers to a list one by one. In Scala you can just do

This gives the same result as 1.to(100): an immutable Range from 1 to 100 that we can map or filter as necessary.

What if instead we want only multiples of 3, from 3 to 300? There are two ways we can go about it. We could do

This would produce an immutable IndexedSeq[Int] (or IndexedSeq<Integer> in Java parlance, but we’d have to implement IndexedSeq<T> ourselves, or get it from a third party).

If you’re following along on the local Scala REPL, you should see something like this on your command line window:

The other way would be with by(), which operates on a Range.

Technically, a Range generally does not contain every number specified. It only contains the first number (3, in the example), the last number (300) and the step (3). Also, a Range created without an explicit by still has a step: an implicit step of 1.

So, the Range examples presented so far don’t cause the allocation of a hundred slots for instances of Int, just as 1 to Integer.MAX_VALUE would not cause the allocation of 2,147,483,647 slots for instances of Int.

This is why the Scala REPL actually lists every number for the Vector created with map(), but only the beginning and ending numbers (and the step if other than 1) when we use to() to create a Range.

Ideally, the difference between the starting and ending numbers is a multiple of the step, but the Scala REPL will hardly complain if that’s not the case, as the following two examples demonstrate:

When we need the nth number from a Range, it is calculated according to the formula start + (n - 1) * step. Keep in mind that this is zero-indexed, and n must be at least 0 but not more than (end - start)/step.

There are two slightly different ways we can obtain the nth number from a Range, and they differ only in how much we need to type (six keystrokes, as it so happens).

In the following example, we ask for the ninth number of the “serial sevens” (eighth in zero-indexed):

I figure most programmers would rather use the syntax that looks more like array access rather than the apply() syntax. We could be blissfully unaware of apply() if we weren’t interested in implementing something like Range for our own numeric data type.

There are infinitely many rational numbers between any two consecutive integers (irrational numbers also, which are generally dealt with using rational approximations), but no other integers between them.

So it’s not just Int that can have to() implemented. You can use it, for example, on Double if you don’t mind a compiler warning. Also, you must specify a step.

There’s another technicality here: to() for Int actually comes from RichInt, but thanks to a standard implicit conversion, we can use it on instances of Int.

What I’m getting at here is that we can implement to() for Fraction, even though between any two distinct fractions there are infinitely many other fractions. The caller has to specify the step…

Or maybe the step can be inferred. Consider for example the fractions 4/7 and 3/2. The difference between them is 13/14. So maybe our program could infer that the step is 1/14.

Then we would have a list with the following fractions: 4/7, 9/14, 5/7, 11/14, 6/7, 13/14, 1, 15/14, 8/7, 17/14, 9/7, 19/14, 10/7, 3/2.

Actually, it would be some kind of fraction range with start 4/7, end 3/2 and step 1/14. To get, say, the fourth fraction, we’d use the formula 4/7 + 3 × (1/14) = 11/14.

If these fractions look familiar, it might be because they come from testTo() in the previous article, which I now repeat here:

And this was the stub to fail the first test:

Where I left off in the previous article, testTo() was failing. Also testCompareTo(), which may or may not have important consequences for our implementation of to().

I also mentioned that I don’t like to() returning a mutable collection. It seems to me now that what we need to do here is implement AbstractSeq[Fraction]. Or maybe IndexedSeq[Fraction]?

Also, now that I have IntelliJ with Scala set up on a MacBook, I don’t really feel like running JUnit on the Windows command line anymore, so I’m going to write the rest of this article with the IntelliJ installation of JUnit rather than JUnit itself directly on the command line.

I think the first thing we need to do is implement a “static function” that will infer the step between two fractions. In Java parlance, this would be a “static method.” In Scala, then, this would go in our Fraction object.

Here’s that stub in context:

The test, which the stub will fail, goes in the FractionTest class in the fractions package of the test packages.

And here is inferStep() rewritten to pass the test:

Hmm… I just noticed a problem here as I was rereading this article when I thought it was ready for publication.

That last output ought to be −1/12, not 1/12. I’ll have to write a test for that case. It shouldn’t take too long, but I don’t want to delay publication too much longer, so for now it’s an exercise you can do if you care to.

With inferStep() passing the test, the next step is to design our equivalent of Range for Fraction, which I have predictably named FractionRange. Chained constructors in Scala are slightly different from Java’s, but the basic principle is the same.

This should fail all of our tests. Comparisons of different FractionRange objects will erroneously return true, apply() will always give 0 instead of the correct Fraction, and by() will give the same FractionRange.

Also, we’re not overriding toString() or hashCode() yet, so the tests for those will also fail.

Next, we add some private fields to the primary constructor, and stubs for the toString() and hashCode() overrides.

Finally,

This should pass all the tests. For refactoring, it would be nice if the chained constructor didn’t cause inferStep() to be called twice on the same starting and ending fractions.

Or we could decide that this inferred step feature is not a feature FractionRange should actually have, in which case we would adjust our tests accordingly and then remove that functionality.

For now, though, I would rather move on to the last piece of this puzzle, which is implementing Fraction.to(). Now that we have FractionRange, we can chuck the java.util.ArrayList import and change our Fraction.to() stub to use FractionRange instead.

Likewise testTo() will need to be changed as well:

This test will still fail, but the fix is very easy now. If you’re using NetBeans, you might be reminded that testCompareTo() is still failing (if you haven’t done anything about it), but that’s gonna have to be a topic for another day. The corrected to() is actually shorter than the failing stub:

The test should now pass. You can also play with this in the Scala REPL if you like (it might be a good idea to quit and restart the REPL if an older version of the fractions package is in the REPL’s current classpath).

Another deficiency I noticed at the last minute during my final pre-publication review concerns the IndexOutOfBoundsException.

This is as it should be, since index 10 would correspond to 11, which is beyond the specified endpoint. Compare and contrast to:

The IndexOutOfBoundsException should have occurred for res48(10), since that would refer to the 11th element of a 10-element sequence, but instead it gave the result 11/10.

In this context, precision and consistency would be preferable to the slight generosity. This is something else that I will take care of after publishing this article, and which so can be another optional exercise for you.

Lastly, just as using map() or filter() on a Range of Int creates an IndexedSeq[Int], so does using map() or filter() on a FractionRange creates an IndexedSeq[Fraction].

In this next example from the REPL, res14 refers to the FractionRange from 4/7 to 3/2.

We get this functionality for free just by having FractionRange extend IndexedSeq[Fraction]. No need to reinvent the wheel of map() or filter() or any of the other amenities of the IndexedSeq[A] trait (see the documentation for the others).

is a composer and photographer from Detroit, Michigan. He has been working on a Java program to display certain mathematical diagrams.