Statically Typed Scala Tuples : So much for good things in small packages

As developers we always face a situation where we have to return more than one value from a method. If we are programming in Java then you can only think of a POJO solution. You would have to create a class to group these values however disparate and you will have to think a lot what to name this class. Even if these values doesn't constitute a class in Object Oriented sense we will have to create one while coding in Java.

The disadvantage of such POJOs is the clutter they create as we browse classes in Eclipse package explorer. They are present because the language (Java) doesn't provide tools to model these really ad-hoc types. As a result these become permanent types. They are not a model of real world into Object Oriented System being designed. They are not even part of the Design.

Scala comes with a nice solution to this problem with the Tuple type. In Scala you can group a set of values together to create a Tuple object. Scala compiler based on the type of values and the order will infer the Type of the Tuple. So you get to return multiple values from a method and probably pass multiple values together to a function. Or in a function you need to temporarily group certain values together. It saves you unnecessary classes and removes clutter and allows you concentrate on business logic.

A tuple is a finite element container of possibly heterogeneous types.Like lists, tuples are immutable, but unlike lists, tuples can contain different types of elements. To instantiate a new tuple that holds some objects, just place the objects in parentheses, separated by commas. Once you have a tuple instantiated, you can access its elements individually with a dot, underscore, and the one-based index of the element.

val pair = (10,"Apples")
println(pair._1)
println(pair._2)

We just created a tuple and assigned a reference named pair to it. The tuple contains two elements. The first being an Int and second a String. You can access elements of a tuple with one based index interface methods such as _1,_2,_3. Scala infers the type of the tuple to be Tuple2[Int, String], and gives that type to the variable pair. The actual type of a tuple depends on the number of elements it contains and the types of those elements. Scala library has defined Tuple classes upto Tuple22. Tuple2 class for example is a Tuple2[A,B] parametrized class which infers the type of the elements to be Int and String in the case above.

Now lets say if you have a class Circle which needs to return its Center. Immediately you will think about a class named Point with x and y values. In Scala you can get away with defining a Point class by just returning a tuple.

class Circle {
  private val radius = 20
 
  def center():(Int, Int) = {
    var x = 10
    var y = 20
    (x, y)
  }
}

You can create tuples in scala with a "->" method.

scala> 1->2
res0: (Int, Int) = (1,2)

How this works is out of scope for this blog post. Using -> method is common for defining key value pairs in a map.

scala> val m = Map(1->2, 3->4)
m: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

Tuples are also useful while doing Pattern Matching, For Comprehensions in Scala. I will try and discuss their use when I visit Pattern Matching and For Comprehensions.

Scala List's 'Prepend' Smartness

Do you remember Time Complexity and the ever complex O notation? Well if you do not let me remind you of that. Remember Semester 3 course Computer Algorithms? Well you got it. Wiki definition of Complexity says : "In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem."

If you have written those for loops which traverse lists or array to search an element in them or to add an element at the end you already know that the Time required to traverse a list grows with its size. Well what you were doing was a linear search and A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does. It is true for implementations of Lists or Array's in programming languages.

Here Scala's List comes to your rescue. Scala's List type allows you to create an immutable list of items.

val oneTwoThree = List(1, 2, 3)

The most common operation on scala List is ‘::’, which is pronounced “cons.” Cons prepends a new element to the beginning of an existing list, and returns the resulting list. For example, if you run this script:

val twoThree = List(2, 3)
val oneTwoThree = 1 :: twoThree
println(oneTwoThree)

You’ll see:

List(1, 2, 3)

In the expression “1 :: twoThree”, :: is a method of its right operand, the list, twoThree. You might suspect there’s something amiss with the associativity of the :: method, but it is actually a simple rule to remember: If a method is used in operator notation, such as a * b, the method is invoked on the left operand, as in a.*(b)—unless the method name ends in a colon. If the method name ends in a colon, the method is invoked on the right operand. Therefore, in 1 :: twoThree, the :: method is invoked on twoThree, passing in 1, like this: twoThree.::(1).

The time it takes to append to a list grows linearly with the size of the list, whereas prepending with :: takes constant time. So in Scala whenever you want to work with a sequence of items or build it, if you use Scala List you could achieve building a list in Constant time no matter what is the size of the list.

Scala's Characteristics

Scala is for Scalable Language. A language which allows you to scale up or down your software development. Scalability is influenced by many factors, ranging from syntax details to component abstraction constructs. Scala fuses Object Oriented and Functional paradigms together. In Scala we have Function is-a Value is-a Objects. So Functions are values and values are objects.

Scala is object-oriented: In Scala everything is an object. Unlike Java which has non object oriented impurities in terms of static values and methods as well as primitive types which are not objects, Scala creates constructs which satisfy the use cases of static values and methods with companion objects. In Scala there are no primitive types and everything is an object.

Scala is an object-oriented language in pure form: every value is an object and every operation is a method call. For example, when you say 1 + 2 in Scala, you are actually invoking a method named + defined in class Int. You can define methods with operator-like names that clients of your API can then use in operator notation.

Scala is Functional : A functional language has a Function is a value which is of same status as say integer. You can pass functions as arguments to other functions, store them in variables and return them as results of other functions. The second main idea of functional programming is that the operations of a program should map input values to output values rather than change data in place. So one should in a position to substitute a function call with its result without affecting semantics.

Other advantages of Scala is that its compatible with Java, Its concise and its Statically typed.


In the next post I plan to dig into the basics of langauge taking a step at a time.

Scala to solve Mars Rover problem

There is a common Mars Rover Problem Developers are asked to code against during Interview Process. Last year I went through one such excersize and submitted my solution in Java. It turned out to be 10 Java classes long and almost same number of files.

Now that I am learning Scala, I thought instead of writing the Hello World program in Scala how would it be to design the solution to the same problem. It took me a day to get it right but amazingly the solution was terse one file long with one Scala application class and many Scala object singletons.

Here is the problem and the Scala solution to it.

The Problem

A squad of robotic rovers are to be landed by NASA on a plateau on Mars. This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.
A rover’s position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North.
In order to control a rover, NASA sends a simple string of letters. The possible letters are ‘L’, ‘R’ and ‘M’. ‘L’ and ‘R’ makes the rover spin 90 degrees left or right respectively, without moving from its current spot. ‘M’ means move forward one grid point, and maintain the same heading.
Assume that the square directly North from (x, y) is (x, y+1).
INPUT: The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.
The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover’s position, and the second line is a series of instructions telling the rover how to explore the plateau.
The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover’s orientation.
Each rover will be finished sequentially, which means that the second rover won’t start to move until the first one has finished moving.
OUTPUT The output for each rover should be its final co-ordinates and heading.
INPUT AND OUTPUT

Test Input:
5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM

Expected Output:

1 3 N
5 1 E

object RoverApplication {
  
  sealed abstract class Direction(val dx:Int, val dy: Int, left: => Direction) {
    lazy val turnLeft = left
    lazy val turnRight = turnLeft.turnLeft.turnLeft
  }
  case object North extends Direction(0, 1, West)
  case object West extends Direction(-1, 0, South)
  case object South extends Direction(0,-1, East)
  case object East extends Direction(1,0, North)
  
  val directions = List(North, West, South, East)
  
  case class Position(x: Int, y: Int) {
    def moveBy(dir:Direction) = copy(x + dir.dx, y + dir.dy)
    override def toString = "(%d/%d)".format(x, y)
  }
  
  case class Rover(position: Position, direction: Direction) {
    def moveForward = copy(position moveBy direction)
    def turnLeft = copy(direction = direction.turnLeft)
    def turnRight = copy(direction = direction.turnRight)
  
    val commands = Map('M' -> moveForward _, 'L' -> turnLeft _, 'R' -> turnRight _)
    def move(directions: String): Rover =
      directions.foldLeft(this){ _.commands(_).apply }
  
    override def toString = "Rover is at %s, looking %s".format(position, direction)
  }
  
  def main(args: Array[String]) {
    val input = List("5 5", "1 2 N", "LMLMLMLMM", "3 3 E", "MMRMMRMRRM")
    val Array(plateauHight, plateauWidth) = input.head split ' '
  
    val roversAndCommands = 
      for (List(orientation, commands) <- input.tail grouped 2) yield {
        val Array(x, y, d) = orientation split ' '
        val position = Position(x.toInt, y.toInt)
        (Rover(position, directions.find(_.toString.startsWith(d)).get), commands)
      }
  
    for ((rover, commands) <- roversAndCommands)
      println(rover move commands)
  }
  
}