Scala fraction addition

Question

This just adds fractions. For example, if we have a text file with:

1/3
1/2

It will print:

5/6

I would love to hear some remarks on how I can make this more Scala-like.

class Fraction(c: BigInt, d: BigInt) {
  val divisor = c.gcd(d);
  def counter = c / divisor;
  def denominator = d / divisor;

  def lcm(a: BigInt, b: BigInt):BigInt = (a * b).abs / a.gcd(b)

  def + (f: Fraction): Fraction = {
    val lcmVal = lcm(f.denominator, denominator)
    val apply = (count: BigInt, div: BigInt) => lcmVal / div * count
    new Fraction(
      apply(f.counter, f.denominator)
        + apply(counter, denominator)
      , lcmVal)
  }

  override def toString(): String = {
    return String.format("%s / %s", counter, denominator)
  }
}

object AddingFractions {

  def sumFractions(fractions: Array[Fraction]): Fraction = {
    val sum = fractions(0) + fractions(1)
    if (fractions.length > 2) {
      return sumFractions(sum +: fractions.slice(2, fractions.length))
    }
    sum
  }

  def main(args: Array[String]): Unit = {
    val lines = scala.io.Source.fromFile(args(0)).getLines()
    val linesArray = lines.toArray

    val fractions = linesArray
      .map((s: String) => s.split("/"))
      .map((ar: Array[String]) => Array(Integer.parseInt(ar(0)), Integer.parseInt(ar(1))))
      .map((iar: Array[Int]) => new Fraction(iar(0), iar(1)))

    println(sumFractions(fractions))
  }
}

Answer 1

Basic problems with input

Your code will blow up if there are fewer than two fractions in the input. Even @janos's solution (which can cope with only one fraction) fails if there are no fractions in the input. Is that reasonable, especially given that the sum of no numbers at all is 0?

Your code also fails on any badly formatted input but there's enough else to talk about to leave that for another day.

Style

apply method

It's common practice in Scala, with types like your Fraction, to add an apply method to dispense with the need for new. It can be added directly to the class or in a companion object.

object Fraction {
  def apply(c: BigInt, d: BigInt) = new Fraction(c, d)
}

With the apply method added, Fraction(1,2) will return Fraction = 1 / 2 with no need for new. It's a minor convenience, in the case of your simple class, but feels more natural.

Note: It would also be very useful to add an unapply method, for pattern matching. Ask if you need details.

Implicit conversions

This is not necessary for the scope of your current, simple code but if you intend to do more with your Fraction, it may be useful to be able to add fractions and integers and get fractions as a result). If you add one simple method to your class...

  def + (i: Int): Fraction = this + (new Fraction(i, 1))

then Fraction(1, 2) + 1 will return Fraction = 1 / 2. However, 1 + Fraction(1, 2) will not work, because Int has no + method which takes a Fraction parameter. This can be fixed by creating an Int-wrapping class which does have such a method and creating an implicit conversion which can turn an Int into such a class. To make this magic optional rather than an unexpected surprise, put them into a companion object, thus:

object Fraction {
  def apply(c: BigInt, d: BigInt) = new Fraction(c, d)
  // Implicit classes added in Scala 2.10
  implicit class FractionalInt(i: Int) {
    def + (that: Fraction) = that + i
  }
}

Now anybody using your Fraction code can choose to do import Fraction._, after which 0 + Fraction(1,2) will return Fraction = 1 / 2

Pattern matching in explicit recursion

As Janos said, the best solution is a higher-order function but if you are going to do explicit recursion, pattern matching is often much more expressive and clean, as in

def sumFractions(fractions: Array[Fraction]): Fraction =
  fractions match {
    Array() => new Fraction(0, 1)
    Array(x) => x
    Array(x, y) => x + y
    Array(x, y, _*) => sumFractions((x + y) +: (fractions drop 2))
  }

Note that

1. This copes with 0 or 1 entries
2. I could have left the third match out and it would still work

This style is more expressive and less fragile than your imperative implementation.

Make functions generic

Later I'm going to argue that arrays are no benefit at all anywhere in your current code, but my point now is that sumFractions should not dictate that it be passed an array. janos's solution only really requires a Seq - and so does your explicitly recursive solution, as discussed elsewhere in this answer.

Janos's solution could be rewritten as

def sumFractions(fractions: Seq[Fraction]) : Fraction =
  fractions.reduceLeft(_ + _)

and nothing would break, because in Scala Array implements the Seq trait. Any Seq-derived type will have reduceLeft, so there is no reason for this function to demand one. That gives you much more freedom in the rest of your code. If you decide to switch from arrays to sets or lists, this function does not then have to be rewritten.

Note: my pattern-matching variant on your explicitly recursive function can also be rewritten to be more generic. Can add an example if you want.

sumFractions is redundant

Your class deals with a particular representation of rational numbers. I've already mentioned that it might be useful (via implicits) to make them work with integers. However, if you go further and do the work to make Fraction part of Scala's Numeric type class, then pretty much anything you can do with a sequence of Int (or Double or other numeric types) can be done with a sequence of Fraction. If you do that work, you can simply replace sumFractions with fractions.sum. Here's one way how

/* This could be placed inside the companion object
implicit object NumericFraction extends Numeric[Fraction] {
  def plus(x: Fraction, y: Fraction): Fraction = x + y
  /* Actually, there's a whole extra bunch of abstract
   * methods that you have to implement - see later
   */
}

Once this is done, assuming fractions is a sequence of Fractions (Seq[Fraction], List[Fraction], Array[Fraction] or whatever) then you can throw away sumFractions and simply use

fractions.sum

But there's more. To actually make Fraction numeric, you have to implement the rest of the type class. Here's an extended version of the companion object, which does just that, without adding any more methods to your original class:

object Fraction extends Numeric[Fraction] {
  def apply(c: BigInt, d: BigInt) = new Fraction(c, d)

  implicit object NumericFraction extends Numeric[Fraction] {
    // Required by scala.math.Numeric
    def fromInt(x: Int): Fraction = Fraction(x, 1)
    def minus(x: Fraction, y: Fraction): Fraction = x + negate(y)
    def negate(x: Fraction) = Fraction( - x.counter, x.denominator)
    def plus(x: Fraction, y: Fraction): Fraction = x + y
    def times(x: Fraction, y: Fraction): Fraction =
      Fraction(x.counter * y.counter, x.denominator * y.denominator)
    def toDouble(x: Fraction): Double =
      x.counter.toDouble / x.denominator.toDouble
    def toFloat(x: Fraction): Float =
      x.counter.toFloat / x.denominator.toFloat
    def toInt(x: Fraction): Int = (x.counter / x.denominator).toInt
    def toLong(x: Fraction): Long = (x.counter / x.denominator).toLong
    // Required by scala.math.Ordering
    def compare(x: Fraction, y: Fraction) =
      (x.counter * y.denominator) compare (y.counter * x.denominator)
  }
}

Once that is done, you get to do all this:

scala> val fractions = List(Fraction(1,2), Fraction(1,3), Fraction(1,4))
fractions: List[Fraction] = List(1 / 2, 1 / 3, 1 / 4)

scala> fractions.sum
res1: Fraction = 13 / 12

scala> fractions.product
res2: Fraction = 1 / 24

scala> fractions.min
res3: Fraction = 1 / 4

scala> fractions.max
res4: Fraction = 1 / 2

scala> fractions.sorted
res5: List[Fraction] = List(1 / 4, 1 / 3, 1 / 2)

I did this using a companion object, which is easier because it doesn't require modification of the original class. This is the conventional way in which type classes are used. Although I have been able to implement all the Numeric abstract methods using only your + method, it would be useful to add native /, *, - methods to Factor and rewrite the implicit type class instance to call them.

The important point is that what I have shown you is really very little extra work and immediately gives you the use of many built in functions from the collections api.

Arrays are not appropriate here

Did you use arrays simply because you aren't very familiar with pattern matching but understand pulling elements from an array? There really is almost no benefit at all to using arrays here. Arrays only offer an advantage where random access is needed to a collection of fixed size. Your use of the collections is entirely sequential

sumFractions

As covered above, sumFractions need specify nothing more than Seq[Fraction as input. The reduceLeft solution will use the appropriate, optimised implementation of whichever sequence you pass in. Even with explicit recursion (example provided on demand), the solution can be generalised to Seq without demanding by default all the copying required by Array.

Even if you choose to optimise the file input and parsing step with parallel collections, sumFractions need not know.

LinesArray not necessary

Any sequence (and other collections) can be mapped over. As explained, sumFractions does not need an array. Even if it did, you could convert to an array at the end of input processing. Also, consider that some of the lines may be invalid. You may choose either to halt at the first error or discard invalid lines; in either case, converting to an array first would be a waste of effort.

Parsing

Ah, now, split does offer a simple way to parse the input lines. If you want to handle only perfectly formatted lines (not even permitting whitespace) and halt/crash on bad ones, it will do the job. Although your current implementation actually does tolerate some possible bad lines.

Processing the input

Halting on the first error

Efficiency

You perform a series of maps. Each one creates a complete new collection before the next is applied. If the first line is poorly formatted and there are 20000 lines in the file, your first map will split all 20000 lines before crashing when it cannot parse that first line. Worse, if the first line is "1/0", which is well formatted but not a valid Fraction, the code will split 20000 lines, then parse 20000 Array[String]s and only then halt on the first invalid input.

The solution is to start with lines.view. A view is a lazy version of the collection. If you apply a transformation (e.g map or filter), what you receive is not a transformed collection but a new view with all the original items, each of which will not be transformed until you access it. If you apply a second transformation, you receive yet another view, still with the original items but now with with two transformations which will be applied in sequence (in other words, they have been composed into a new function) to each item as you access it. And so on.

So if we change your code to

val fractions = lines.view splitLines parseInts makeFractions 

(for simplicity, assume we have created 3 functions which implement your 3 transformations) then fractions will still be untransformed in reality, waiting to apply all 3 transformations to any item you ask for. So if you then do

`sumFractions(fractions)` // A SeqView is still a Seq

or (if you've implemented the Numeric type class for Fraction)

fractions.sum

then it will start by applying all 3 transformations to the first line. If that line is "3/0", the program will halt without touching the rest, saving a lot of time.

Catching more bad lines

Your code will tolerate "1/2/3" or "1/2/ gibberish" as input lines, converting them both to Fraction(1,2). That is because it asks for the first two elements This can be avoided with pattern matching and a partial function. So the second, parseInts transformation could be rewritten with

map { case Array(x, y) => Array(x.toInt, y.toInt) }

or

map { case ar@Array(x, y) => ar map { _.toInt } }

Because this uses a partial function, if any input line does not split into an array of precisely 2 items then the program will throw a MatchError.

Pattern matching this way is expressive and succinct enough to combine the second and third transformations. So we could replace both parseInts and makeFractions with

map { case Array(x, y) => new Fraction(x.toInt, y.toInt) }

Although this may give you concise code at the expense of flexibilty, particularly if you want to report meaningful errors (more later on that).

Regex rather than Split

Regexes offer at least three possible advantages

1. The option to tolerate whitespace in your input
2. Powerful pattern matching

3. Easier error reporting

   val fractionLine = """(\d+)/(\d+)""".r

creates a pattern which is even more useful than split "/" because it only matches properly formatted lines with genuine numbers in them. Optionally,

val fractionLine = """\s*(\d+)\s*/\s*(\d+)\s*""".r

accepts harmless whitespace. The first transformation could be rewritten as

map { case fractionLine(x, y) => Array(x, y) }

the first two as

map { case fractionLine(x, y) => Array(x.toInt, y.toInt) }

or all three to

map { case fractionLine(x, y) => new Fraction(x.toInt, y.toInt) }

Again, combining these functions may be concise but may hinder debugging or error reporting.

Meaningful errors

A simple way to provide better error reporting is to turn the partial functions into complete functions, raising errors when no match is made. So the regex version of the first transformation could become

map {
  case fractionLine(x, y) => Array(x, y)
  case s => throw new MyException("Invalid input line:'" + s + "'")
}

Similarly, the second transformation could throw an exception if the input doesn't match Array(x, y) and the third could complain if the divisor is 0.

Another way to add useful information to error reporting would be to add zipWithIndex as a new, first transformation so that the number of the line in the file is available.

Note that combining two or three of the transformations into one would make the error-handling pattern matching more complex and fragile, although not combining them would make it more complex to report the line number and line content if the failure was in the later transformations.

There are more functional ways to deal with errors but that's a more complex topic.

Answer 2

sumFractions can be simplified quite a bit:

def sumFractions(fractions: Array[Fraction]): Fraction = 
  fractions.reduceLeft(_ + _)

And there are several Java elements that could be simply removed:

• Semicolons terminating statements
• return statements

Lastly, I think the official term is "numerator" instead of "counter". And I would rename "divisor" to "gcd".