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 100This 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 3Technically, 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 = inexact Range 1 to 100 by 13scala> 100 to 1 by -7
res7: scala.collection.immutable.Range = inexact Range 100 to 1 by -7
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):
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
= 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 // Chained constructor
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 = false override def hashCode: Int = 0 override 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 "
+ this.endFraction.toString
if (!this.inferredStepFlag) {
rangeString = rangeString + " by "
+ this.stepFraction.toString
}
rangeString
} override def equals(obj: Any): Boolean = obj match {
case obj: FractionRange => this.startFraction
== obj.startFraction && this.endFraction
== obj.endFraction && this.stepFraction == obj.stepFraction
case _ => false
} override def hashCode: Int = (this.endFraction.hashCode
- this.startFraction.hashCode) * this.stepFraction.hashCode override def length: Int = this.len override 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).