# Implementing ranges of fractions in Scala

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

`1 to 100`

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

`(1 to 100).map(3 * _)`

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:

`scala> (1 to 100).map(3 * _)`

res4: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204, 207, 210, 213, 216, 219, 222, 225, 228, 231, 234, 237, 240, 243, 246, 249, 252, 255, 258, 261, 264, 267, 270, 273, 276, 279, 282, 285, 288, 291, 294, 297, 300)

The other way would be with `by()`

, which operates on a `Range`

.

`scala> (3 to 300) by 3`

res5: scala.collection.immutable.Range = Range 3 to 300 by 3

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:

scala> 1 to 100 by 13

res6: scala.collection.immutable.Range =inexactRange 1 to 100 by 13scala> 100 to 1 by -7

res7: scala.collection.immutable.Range =inexactRange 100 to 1 by -7

When we need the `n`

th 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 `n`

th 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):

scala> res7.apply(8)

res8: Int = 44scala> res7(8)

res9: Int = 44

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.

scala> 0.5 to 3.5 by 0.25

<console>:12: warning: method to in trait FractionalProxy is deprecated (since 2.12.6): use BigDecimal range instead

0.5 to 3.5 by 0.25

^

res10: scala.collection.immutable.NumericRange[Double] = NumericRange 0.5 to 3.5 by 0.25scala> res10(0)

res11: Double = 0.5scala> res10(1)

res12: Double = 0.75scala> res10(2) // You get the idea

res13: Double = 1.0

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:

` @Test def testTo: Unit = {`

import java.util.ArrayList

val fourSevenths = new Fraction(4, 7)

val threeHalves = new Fraction(3, 2)

val expected = new ArrayList[Fraction]

for (n <- 8 to 21) expected.add(new Fraction(n, 14))

val actual = fourSevenths to threeHalves

assertEquals(expected, actual)

}

And this was the stub to fail the first test:

import java.util.ArrayList def to(end: Fraction): ArrayList[Fraction] = {

var range = new ArrayList[Fraction]

range.add(this)

range

}

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()`

.

JUnit version 4.12

..........E.E..Trying to divide by zero correctly triggered IllegalArgumentException: Dividing 3/2 by 0 results in an indeterminate number.

....

Time: 1.875

There were 2 failures:

1)testTo(fractions.FractionTest)

java.lang.AssertionError: expected:<[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]> but was:<[4/7]>

2)testCompareTo(fractions.FractionTest)

java.lang.AssertionError: The test case is a prototypeFAILURES!!!

Tests run: 17, Failures: 2

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:

object Fraction { val HASH_SEP = 65536 import scala.language.implicitConversions implicit def IntToFraction(n: Int): Fraction = new Fraction(n)def inferStep(startFract: Fraction, endFract: Fraction): Fraction}

= new Fraction(0)

The test, which the stub will fail, goes in the `FractionTest`

class in the `fractions`

package of the test packages.

` @Test def testInferStep(): Unit = {`

println("inferStep")

val begin = new Fraction(7, 12)

val finish = new Fraction(13, 12)

var expected = new Fraction(1, 12)

var actual = Fraction.inferStep(begin, finish)

assertEquals(expected, actual)

actual = Fraction.inferStep(finish, begin)

assertEquals(expected, actual)

val altBegin = new Fraction(5, 8)

expected = new Fraction(1, 24)

actual = Fraction.inferStep(altBegin, finish)

assertEquals(expected, actual)

actual = Fraction.inferStep(finish, altBegin)

}

And here is `inferStep()`

rewritten to pass the test:

object Fraction { val HASH_SEP = 65536 import scala.language.implicitConversions implicit def IntToFraction(n: Int): Fraction = new Fraction(n) def inferStep(startFract: Fraction, endFract: Fraction):

Fraction = {

if (startFract.denominator == endFract.denominator) {

new Fraction(1, startFract.denominator)

} else {

val diff = endFract - startFract

val inferredStep = new Fraction(1, diff.denominator)

if (endFract > startFract) {

inferredStep

} else {

-inferredStep

}

}

}}

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

scala> numberA = new fractions.Fraction(4, 7)

numberA: fractions.Fraction =4/7scala> numberB = new fractions.Fraction(3, 2)

numberB: fractions.Fraction =3/2scala> fractions.Fraction.inferStep(numberA, numberB)

res39: fractions.Fraction =1/14scala> fractions.Fraction.inferStep(numberB, numberA)

res40: fractions.Fraction =-1/14scala> numberA = new fractions.Fraction(7, 12)

numberA: fractions.Fraction =7/12scala> numberB = new fractions.Fraction(13, 12)

numberB: fractions.Fraction =13/12scala> fractions.Fraction.inferStep(numberA, numberB)

res41: fractions.Fraction =1/12scala> fractions.Fraction.inferStep(numberB, numberA)

res42: fractions.Fraction =1/12

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.

package fractionsclass FractionRange(start: Fraction, end: Fraction, step: Fraction) extends IndexedSeq[Fraction] {

val startFraction: Fraction = start

val endFraction: Fraction = end

val stepFraction: Fraction = step // Chained constructor

def this(start: Fraction, end: Fraction) {

this(start, end, Fraction.inferStep(start, end))

} override def equals(obj: Any): Boolean = obj match {

case obj: FractionRange => true

case _ => false

} override def length: Int = 0 override def apply(idx: Int): Fraction = new Fraction(0) def by(newStep: Fraction): FractionRange = this}

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.

package fractionsimport org.junit.Test

import org.junit.Assert._class FractionRangeTest { @Test def testConstructor(): Unit = {

println("constructor")

val begin = new Fraction(5, 8)

val finish = new Fraction(7, 8)

val invalidStep = new Fraction(3, 2)

try {

val fractionRange = new FractionRange(begin, finish,

invalidStep)

val failMsg = "Should not have been able to construct "

+ fractionRange.toString + " with invalid step "

+ invalidStep.toString

fail(failMsg)

} catch {

case iae: IllegalArgumentException =>

println("Trying to construct FractionRange with invalid step "

+ invalidStep.toString + " correctly triggered

IllegalArgumentException")

println("\"" + iae.getMessage + "\"")

case e: Exception => val failMsg = e.getClass.getName

+ " is wrong exception for trying to construct

FractionRange with invalid step "

+ invalidStep.toString + "."

fail(failMsg)

}

} @Test def testToString(): Unit = {

println("toString")

val begin = new Fraction(7, 12)

val finish = new Fraction(13, 12)

var fractionRange = new FractionRange(begin, finish)

var expected = "7/12to13/12"

var actual = fractionRange.toString.replace(" ", "")

assertEquals(expected, actual)

val newStepSize = new Fraction(1, 24)

fractionRange = new FractionRange(begin, finish, newStepSize)

expected = "7/12to13/12by1/24"

actual = fractionRange.toString.replace(" ", "")

assertEquals(expected, actual)

} @Test def testEquals(): Unit = {

println("equals")

val begin = new Fraction(7, 12)

val finish = new Fraction(13, 12)

val fractionRange = new FractionRange(begin, finish)

val explicitStep = new Fraction(1, 12)

val sameFractionRange = new FractionRange(begin, finish,

explicitStep)

assertEquals(fractionRange, sameFractionRange)

val diffFractionRange = new FractionRange(explicitStep, finish)

assertNotEquals(fractionRange, diffFractionRange)

} @Test def testHashCode(): Unit = {

println("hashCode")

val begin = new Fraction(7, 12)

val finish = new Fraction(13, 12)

val fractionRange = new FractionRange(begin, finish)

val explicitStep = new Fraction(1, 12)

val sameFractionRange = new FractionRange(begin, finish,

explicitStep)

assertEquals(fractionRange.hashCode, sameFractionRange.hashCode)

val diffFractionRange = new FractionRange(explicitStep, finish)

assertNotEquals(fractionRange.hashCode,

diffFractionRange.hashCode)

println(fractionRange.toString + " hashed as "

+ fractionRange.hashCode)

println(diffFractionRange.toString + " hashed as "

+ diffFractionRange.hashCode)

} @Test def testLength(): Unit = {

println("length")

val begin = new Fraction(7, 12)

val finish = new Fraction(13, 12)

var fractionRange = new FractionRange(begin, finish)

var expected = 7

var actual = fractionRange.length

assertEquals(expected, actual)

val newStepSize = new Fraction(1, 24)

fractionRange = new FractionRange(begin, finish, newStepSize)

expected = 13

actual = fractionRange.length

assertEquals(expected, actual)

} @Test def testApply(): Unit = {

println("apply")

val begin = new Fraction(7, 12)

val finish = new Fraction(13, 12)

var fractionRange = new FractionRange(begin, finish)

for (n <- 7 to 13) {

val expected = new Fraction(n, 12)

val actual = fractionRange.apply(n - 7)

assertEquals(expected, actual)

}

val newStepSize = new Fraction(1, 24)

fractionRange = new FractionRange(begin, finish, newStepSize)

for (m <- 14 to 26) {

val expected = new Fraction(m, 24)

val actual = fractionRange.apply(m - 14)

assertEquals(expected, actual)

}

try {

val result: Fraction = fractionRange.apply(-1)

val failMsg = "Trying to apply index -1 to range "

+ fractionRange.toString +

" should have caused an exception, not given result "

+ result.toString

fail(failMsg)

} catch {

case ioobe: IndexOutOfBoundsException =>

println("Trying to apply index -1 to range "

+ fractionRange.toString + " correctly caused

IndexOutOfBoundsException")

println("\"" + ioobe.getMessage + "\"")

case e: Exception => val failMsg = e.getClass.getName

+ " is wrong exception for trying to apply index -1 to range "

+ fractionRange.toString + "."

fail(failMsg)

}

try {

val result: Fraction = fractionRange.apply(200)

val failMsg = "Trying to apply index 200 to range " + fractionRange.toString + " should have caused an exception, not given result " + result.toString

fail(failMsg)

} catch {

case ioobe: IndexOutOfBoundsException =>

println("Trying to apply index 200 to range "

+ fractionRange.toString

+ " correctly caused IndexOutOfBoundsException")

println("\"" + ioobe.getMessage + "\"")

case e: Exception => val failMsg = e.getClass.getName

+ " is wrong exception for trying to apply index 200 to range "

+ fractionRange.toString + "."

fail(failMsg)

}

} @Test def testBy(): Unit = {

println("by")

val begin = new Fraction(0)

val finish = new Fraction(1)

val interval = new Fraction(1, 144)

val initRange = new FractionRange(begin, finish, interval)

val newInterval = new Fraction(1, 16)

val expected = new FractionRange(begin, finish, newInterval)

val actual = initRange.by(newInterval)

assertEquals(expected, actual)

assertNotEquals(initRange, actual)

}}

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

and `hashCode()`

overrides.

package fractionsclass FractionRange(start: Fraction, end: Fraction, step: Fraction)

extends IndexedSeq[Fraction] {

val startFraction: Fraction = start

val endFraction: Fraction = end

val stepFraction: Fraction = step

private[this] val inferredStepFlag: Boolean// Chained constructor

= this.stepFraction

== Fraction.inferStep(this.startFraction, this.endFraction)

private[this] var incr: Fraction

= (this.endFraction - this.startFraction)/this.stepFraction

if (incr.numerator < 0) {

incr = -incr

}

private[this] val len: Int = incr.numerator.toInt + 1

def this(start: Fraction, end: Fraction) {

this(start, end, Fraction.inferStep(start, end))

}override def toString: String = "Not implemented yet"override def equals(obj: Any): Boolean = falseoverride def hashCode: Int = 0override def length: Int = 0 override def apply(idx: Int): Fraction = new Fraction(0) def by(newStep: Fraction): FractionRange = this}

Finally,

package fractionsclass FractionRange(start: Fraction, end: Fraction, step: Fraction)

extends IndexedSeq[Fraction] {

val startFraction: Fraction = start

val endFraction: Fraction = end

val stepFraction: Fraction = step

private[this] val inferredStepFlag: Boolean

= this.stepFraction

== Fraction.inferStep(this.startFraction, this.endFraction)

private[this] var incr: Fraction

= (this.endFraction - this.startFraction)/this.stepFraction

if (incr.denominator != 1) {

val excMsg = "Step " + step.toString

+ " is invalid for FractionRange from "

+ start.toString + " to " + end.toString + "."

throw new IllegalArgumentException(excMsg)

}

if (incr.numerator < 0) {

incr = -incr

}

private[this] val len: Int = incr.numerator.toInt + 1 def this(start: Fraction, end: Fraction) {

this(start, end, Fraction.inferStep(start, end))

} override def toString: String = {var rangeString = this.startFraction.toString + " to "} override def equals(obj: Any): Boolean = obj match {

+ this.endFraction.toString

if (!this.inferredStepFlag) {

rangeString = rangeString + " by "

+ this.stepFraction.toString

}

rangeStringcase obj: FractionRange => this.startFraction} override def hashCode: Int =

== obj.startFraction && this.endFraction

== obj.endFraction && this.stepFraction == obj.stepFraction

case _ => false(this.endFraction.hashCodeoverride def length: Int =

- this.startFraction.hashCode) * this.stepFraction.hashCodethis.lenoverride def apply(idx: Int): Fraction = {

if (idx < 0) {

val excMsg = "Negative index " + idx.toString + " is invalid"

throw new IndexOutOfBoundsException(excMsg)

}

if (idx > this.len) {

val excMsg = "Index " + idx.toString

+ " is invalid since range has only "

+ this.len.toString + " elements."

throw new IndexOutOfBoundsException(excMsg)

}

this.startFraction + (this.stepFraction * idx)

} def by(newStep: Fraction): FractionRange = {

new FractionRange(start, end, newStep)

}}

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.

` def to(end: Fraction): `**FractionRange** = {

**new FractionRange(new Fraction(0), new Fraction(0))**

}

Likewise `testTo()`

will need to be changed as well:

` @Test def testTo() {`

val fourSevenths = new Fraction(4, 7)

val threeHalves = new Fraction(3, 2)

**val fractionRange = fourSevenths to threeHalves**

for (n <- 8 to 21) assertEquals(new Fraction(n, 14),

fractionRange(n - 8))

}

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:

`def to(end: Fraction): FractionRange = `**new FractionRange(this, end)**

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).

scala> var numberA = new fractions.Fraction(4, 7)

numberA: fractions.Fraction = 4/7scala> var numberB = new fractions.Fraction(3, 2)

numberB: fractions.Fraction = 3/2scala> numberA to numberB

res14: fractions.FractionRange = 4/7 to 3/2scala> res14(0)

res15: fractions.Fraction = 4/7scala> res14(1)

res16: fractions.Fraction = 9/14scala> res14(2) // And so on and so forth

res17: fractions.Fraction = 5/7

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

.

scala> 1 to 10

res43: scala.collection.immutable.Range.Inclusive = Range 1 to 10scala> res43.size

res44: Int = 10scala> res43(0)

res45: Int = 1scala> res43(9)

res46: Int = 10scala> res43(10)

java.lang.IndexOutOfBoundsException: 10

at scala.collection.immutable.Range.apply$mcII$sp(Range.scala:146)

at scala.collection.immutable.Range.apply(Range.scala:144)

... 28 elided

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

scala> numberA = new fractions.Fraction(1, 10)

numberA: fractions.Fraction = 1/10scala> numberB = new fractions.Fraction(1)

numberB: fractions.Fraction = 1scala> numberA to numberB

res48: fractions.FractionRange = 1/10 to 1scala> res48.size

res49: Int =10scala> res48(9)

res50: fractions.Fraction = 1scala> res48(10)

res51: fractions.Fraction =11/10scala> res48(11)

java.lang.IndexOutOfBoundsException: Index 11 is invalid since range has only 10 elements.

at fractions.FractionRange.apply(FractionRange.scala:47)

... 28 elided

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.

scala> res14.map(_ - 3)

res18: IndexedSeq[fractions.Fraction] = Vector(-17/7, -33/14, -16/7, -31/14, -15/7, -29/14, -2, -27/14, -13/7, -25/14, -12/7, -23/14, -11/7, -3/2)scala> res18.filter(_.numerator % 3 == 0)

res19: IndexedSeq[fractions.Fraction] = Vector(-33/14, -15/7, -27/14, -12/7, -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).