Mark Needham

I was playing around with Scala over the weekend and one thing that I wanted to do was get the data from a HTTP response as a string so that I could parse the xml returned.

The data source is fairly small so loading the stream into memory wasn't a problem.

Carlos pointed me to a bit of Java code that did this and I converted it as literally as possible into Scala.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 def convertStreamToString(is: InputStream): String = {
    val reader = new BufferedReader(new InputStreamReader(is));
    val sb = new StringBuilder();
 
    var line : String = null;
    try {
      while ((line = reader.readLine()) != null) {
        sb.append(line + "\n");
      }
    } catch {
      case e: IOException => e.printStackTrace();
    } finally {
      try {
        is.close();
      } catch {
        case e: IOException => e.printStackTrace();
      }
    }
 
    sb.toString();
  }

The problem with this bit of code becomes clear when we try to run it through the REPL:

7:warning: comparing values of types Unit and Null using `!=' will always yield true
             while ((line = reader.readLine()) != null) {

In Java the expression '(line = reader.readLine())' would return the value of 'reader.readLine()' as far as I understand. We can then compare that to null.

In Scala the evaluation of that expression is 'Unit' so if we ever run this function we end up in an infinite loop and eventually run out of memory.

I rewrote this function making use of recursion to get around the problem:

  def convertStreamToString(is : InputStream) : String = {
    def inner(reader : BufferedReader, sb : StringBuilder) : String = {
      val line = reader.readLine()
      if(line != null) {
        try {
          inner(reader, sb.append(line + "\n"))
        } catch {
          case e : IOException => e.printStackTrace()
        } finally {
          try {
            is.close()
          } catch {
            case e : IOException => e.printStackTrace()
          }
        }
 
      }
      sb.toString()
    }
 
    inner(new BufferedReader(new InputStreamReader(is)), new StringBuilder())
  }

The code is still peppered with error handling statements but it now allows us to convert the stream into a string.

Is there a better/cleaner/more Scala-esque way to do this?

In my continued attempts to learn a bit of Scala I've been trying out the 2nd of Dave Thomas' code katas – Karate Chop – while using an array slicing approach.

I've tried out the iterative approach to this problem in Java about a year ago and it ends up being quite verbose so I thought the array slicing one would be much more concise.

I didn't drive any of the solutions I worked on from the tests – in fact I only got all the tests provided by Dave Thomas running right at the end which was probably a mistake in retrospect.

My first solution didn't really work at all – it resulted in an 'ArrayIndexOutOfBoundsException' for pretty much any input where the 'needle' wasn't the middle value:

def chop(needle : Int, haystack : Array[Int]) : Int  = {
	val middleIndex = haystack.length / 2
	if(haystack(middleIndex) == needle)
		return middleIndex
	else if(haystack(middleIndex) < needle) 
		return chop(needle, haystack.slice(0, middleIndex))
	else
		return chop(needle, haystack.slice(middleIndex + 1, haystack.length))
}

It turns out that the logic is actually the wrong way around – if we find that 'haystack(middleIndex)' is less than 'needle' then we want to be looking at the 2nd half of the array and not the first half!

Attempt number two addressed this problem:

def chop(needle : Int, haystack : Array[Int]) : Int = {
	val midpoint = haystack.length/2
	val valueAtMidpoint = haystack(midpoint)
 
	if(valueAtMidpoint == needle) return midpoint
	else if(valueAtMidpoint > needle) return chop(needle, haystack.slice(0, midpoint))
	else return chop(needle, haystack.slice(midpoint, haystack.length))
}

The problem with this solution is that if the 'needle' is in the second half of the array then it will end up reporting us the wrong position with respect to the whole array – we will just get the position of the 'needle' in the remaining array.

This suggested to me that I would probably need to make use of an inner function to keep track of how many items had been discarded whenever we realised that the item was in the second half of the array.

We could then add that value to the final index position if the 'needle' was found in the array:

def chop(needle : Int, haystack : Array[Int]) : Int = {	
	def chopInner(discardedItems : Int, innerHay : Array[Int]) : Int = {	
		val midpoint = innerHay.length/2
		val originalMidpoint = midpoint + discardedItems
		val valueAtMidpoint = innerHay(midpoint)
 
		if(valueAtMidpoint == needle)  
			originalMidpoint
		else if(valueAtMidpoint > needle)  
			chopInner(0, innerHay.slice(0, midpoint))
		else  
			chopInner(originalMidpoint, innerHay.slice(midpoint, innerHay.length))
	}
	chopInner(0, haystack)
}

This solution will find the position of 'needle' if that value exists in the 'haystack' but if the value isn't in the list we end up in an infinite recursion and if the list is empty then we end up with an 'ArrayIndexOutOfBoundsException' when we try to get the value of the midpoint.

My truly hacky solution which solves these two problems looks like this:

def chop(needle : Int, haystack : Array[Int]) : Int = {	
	def chopInner(discardedItems : Int, innerHay : Array[Int]) : Int = {	
		if(innerHay.length == 0) 	
			return -1
 
		val midpoint = innerHay.length/2
		val originalMidpoint = midpoint + discardedItems
		val valueAtMidpoint = innerHay(midpoint)
 
		if(valueAtMidpoint == needle)  
			originalMidpoint
		else if(valueAtMidpoint > needle)  
			chopInner(0, innerHay.slice(0, midpoint))
		else if(innerHay.length == 1)  
			-1
		else  
			chopInner(originalMidpoint, innerHay.slice(midpoint, innerHay.length))
	}
	chopInner(0, haystack)
}

I converted Dave Thomas' tests into 'specs' tests using the following regular expression:

Find:

assert_equal\((.*),[ ]+chop\((.),[ ]+\[(.*)\]\)\)

Replace:

chop($2, Array($3)) mustBe $1

I then adapted my colleague Sam Newman's bigvisiblewall project so that I could make use of the ant script he's setup which makes specs and ant play nicely together.

All the tests pass but there must be a cleaner solution than what I've ended up with – I think another attempt will be required!

My colleague Liz Douglass and I have been playing around with Scala and Liz recently pointed out Phil Gold's 'Ninety Nine Scala Problems' which we've been working through.

One in particular which is quite interesting is number 7 where we need to flatten a nested list structure.

Therefore given this input:

flatten(List(List(1, 1), 2, List(3, List(5, 8))))

We would expect this output:

res0: List[Any] = List(1, 1, 2, 3, 5, 8)

I tried this out on my own using recursion but kept ending up creating a stack overflow by writing code that never terminated!

We decided to try it out while pairing together using a more imperative approach so that we could get something that actually worked to begin with and ended up with this:

def flatten[A](list : List[A]) : List[A] =  {
 
	var flattenedList : List[A] = Nil
	for(item <- list) {
		item match {
		   case x : List[A] => flattenedList = flatten(x) ::: flattenedList
           case _    => flattenedList = item :: flattenedList
		}
	}
	flattenedList
}

It works and we've got a bit of recursion going on but we're still mutatating the state of a variable so it feels like we're missing out on the strength of a language which provides us with the ability to work in a functional way.

Our second attempt made use of the knowledge we gained from this first attempt with respect to that cases that existed for flattening the list and we made use of a technique which I picked up while learning a bit of F# – the inner function which keeps an accumulator with the flattened list on each recursion:

def flatten[A](list : List[A]) : List[A] = {
	def flat[A](rest : List[A], flattenedList : List[A]) : List[A] = rest match {
			case Nil => flattenedList
			case (head:List[A])::tail =>  flat(tail, flat(head, List()) ::: flattenedList)
			case head::tail => flat(tail, head :: flattenedList) 		
	}
 
	flat(list, Nil).reverse
}

I like the fact that we don't have to mutate any state with this solution but the second case statement is pretty difficult to understand.

We had to distinguish between whether the head of the list was another list or just an element in order to determine whether we needed to break that value down further or just add it to the new list.

Is there a better way to do that than to explicitly state the type of head as we've done here?

Another colleague, Ben Barnard, came over to work with us on the next iteration of this solution which was somewhat driven by seeing how Phil Gold had solved the kth item problem for which he describes a solution which narrows down the initial list each time while still calling the same function:

  def nth[T](n: Int, l: List[T]): T = (n, l) match {
    case (0, e :: _   ) => e
    case (n, _ :: tail) => nth(n - 1, tail)
    case (_, Nil      ) => throw new NoSuchElementException
  }

In this case when we reduce the list we are searching on we also reduce the index that we are looking for by one which works quite nicely.

For the flatten function we were able to recurse on the original function by running the list back through the flatten function whenever we didn't know if the 'head' was an element:

def flatten[A](list : List[A]) : List[A] = list match {
	case Nil => list
	case (head:List[A])::tail => flatten(head) ::: flatten(tail)
	case head::tail => head :: flatten(tail)
}

The nice thing about this solution is that the list is in the correct order at the end so we don't need to reverse it as we did with the previous solutions.

This way of coding is still not quite intuitive to me but I think the solution is cleaner and easier to read than the others.

I've been playing around with Scala a bit and in particular following some of the code examples from Daniel Spiewak's 'Scala for Java Refugees' article on Traits and Types.

One thing that I got a bit confused about in one of the examples was the use of the '_' at the end of one of the function definitions:

class MyContainer[T] {
  private var obj:T = null
 
  def value = obj
  def value_=(v:T) = obj = v
}
 
val cont = new MyContainer[String]
cont.value = "Daniel"
 
println(cont.value)

From my limited understanding of the language the '_' (or placeholder syntax) is often passed to functions when we only want to partially apply the function to its arguments but when you use it in that context there's usually a space between the function name and the '_' so it wasn't being used like that.

From Programming in Scala:

Remember that you need to leave a space between the function name and the underscore, because otherwise the compiler will think you are referring to a different symbol, such as for example, a method named println_, which likely does not exist.

In this example we were able to make use of 'value' without using the '_' though so clearly this was some other syntax I was unaware of.

I came across the idea that it might be linked to 'DynamicVariable' but I think that it's just a coincidence that 'DynamicVariable' happens to define a function called 'value_' since the code described above doesn't mention 'DynamicVariable' anywhere.

Eventually Lars Westergren set me back on track by pointing out that what's being described is a mixed identifier which is a much simpler explanation than what I'd been thinking!

In this case the mixed identifier is 'value_=' which defines an assignment operator which takes in a value 'v' of type 'T' and then assigns it to 'obj'.

It seems quite similar to the way we would use properties in C#.

I'm still finding having so many '=' on the same line to be a bit confusing at the moment so I'd probably rewrite that function like this so it's easier for me to understand:

  def value_=(v:T) = { obj = v }

Channing Walton also linked me to a post which explains how Scala properties work.

In our latest coding dojo we played around with Scala and lambdaj while attempting to solve some of the problems on the Project Euler website.

The Format

We started off on two different machines with two of us having a look at solving the first Project Euler problem in Scala and the other two trying to solve it in Java while using the lambdaj library.

What did we learn?

• Fabio and I worked on the Scala solution to the problem and we were pretty much playing around with different ways to aggregate all the values in the list:

  1.to(999).filter(x => x%3 == 0 || x%5 == 0).foldLeft(0)((acc,x) => acc + x)
  1.to(999).filter(x => x%3 == 0 || x%5 == 0)./:(0)((x,y) => x+y)
  1.to(999).filter(x => x%3 == 0 || x%5 == 0).foldRight(0)(_+_)
  1.to(999).filter(x => x%3 == 0 || x%5 == 0).reduceLeft(_+_)
  1.to(999).filter(x => x%3 == 0 || x%5 == 0)./:(0)(_+_)

  We decided to work through how 'foldLeft' and 'foldRight' work for summing a simpler collection of data, the numbers 1-5, which goes something like this:

  fold_left

  (((((0 + 1) + 2) + 3) + 4) + 5) = 15

  fold_right

  (1 + (2 + (3 + (4 + (5 + 0))))) = 15

  When adding the numbers together it doesn't make any different whether we fold the collection from the left or from the right.

  If we do subtraction we do get different answers though:

  fold_left

  (((((0 - 1) - 2) - 3) - 4) - 5) = -15

  fold_right

  (1 - (2 - (3 - (4 - (5 - 0))))) = 3
   
  -> 5 - 0 = 5
  -> 4 - 5 = -1
  -> 3 - -1 = 4
  -> 2 - 4 = -2
  -> 1 - -2 = 3

  The other way of doing fold_left, '/:', is quite interesting although perhaps unintuitive when you first come across it. Liz showed me an interesting post by Ricky Clarkson where he talks about this method and the reason why it's in the language.

  Liz and Dave Yeung worked on doing a solution to lambdaj to the problem but it ended up being quite verbose so we decided to play around with Scala for the rest of the session.

• We spent a bit of time playing around with traits via a nice introductory article which effectively acts as a a cut down version of the Programming in Scala book.

  I particularly like the way that you can add a trait to an instance of an object and you get access to all the methods defined on that trait which seems quite similar to Ruby mixins.

  Liz and I were discussing an article written by Michael Norton comparing technical debt and making a mess so that's where the trait name came from!

  trait Mess  {
    def makeMess = print("tech debt is so funny")
  }
   
  class Liz {
   
  }

  If you try to make use of the trait like this:

  val liz : Liz = new Liz with Mess

  You don't have access to the 'makeMess' method since you explicitly defined the type to be 'Liz' which doesn't have the method:

  liz.makeMess
  > error: value makeMess is not a member of Liz
         liz.makeMess

  If we let the compiler do its thing without trying to explicitly type the value it works much better:

  val liz = new Liz with Mess
  > Liz with Mess

  liz.makeMess
  > tech debt is so funny

  I really like having the ability to do this although I think I need to code a bit more Scala before I'll appreciate where we really gain by having this feature.

  The conciseness of the language and the lack of '{}' while keeping the same expressiveness in the code is something which reminds me a lot of F# and from what I've seen so far I imagine it would be much more fun to code in Scala than in Java.

  It also seems more clear to me that when a static language has really good type inference then one of the main reasons that people prefer dynamic languages – you get to write less code for the same amount of features – is actually much less valid.

• This was a very experimental dojo in nature although Liz has been playing around with Scala a bit so she was able to guide us a bit when we got stuck.

  I'm finding that sessions where everyone is fairly new to the language or technology aren't necessarily as fruitless as I had previously imagined that they would be – I find that learning something together makes it more interesting as you can then draw on other people's ideas and understanding of the language as well as your own.

  I think in the cases where everyone is a novice people need to be prepared to get involved and write some code despite that. If that's the case then I think it's certainly possible to gain a lot from these sessions.