Fast Track to Haskell Course

I've spent the last two days on a Fast Track to Haskell course. It was a very interesting two days and I learnt a huge amount. The course was taught by Andres Löh from Well-Typed and hosted by the excellent people at Skillsmatter.

I went into the course having read the superb Learn You A Haskell book and having built a couple of experimental Haskell programs. From that starting point there was not a huge amount of content in the course that I was not aware of. However, it was great to have my learning verified and my understanding in many areas significantly improved. There were also a few things that changed my thinking on certain topics. All in all, a well spent two days.

The first day started with a whistle stop tour of the Haskell language and how to build things in it. There were plenty of excellent exercises to help cement learning and understanding. Then we looked in more detail at types and how to reason about software using types. The day concluded with looking at some more advanced type concepts including higher-order functions and type classes. The second day followed on with some more about types and then went on to look at how Haskell deals with I/O (which is very different to most other languages I have encountered). The rest of the day was then spent looking at common patterns that can be found in Haskell code and how these can be generalised into concepts such as Functors and Monads. Plenty more exercises followed.

I will now be going away and working on some private projects in Haskell, with the hope of attending the advanced course some time later this year. In the mean time, this blog post looks at some of the key things that I came away from the course with and how they relate back to the Scala and Java that I tend to do for my day job.

Focus on the Types, they are the API

When using an OO language, such as Java (or even Scala), we tend to think about classes, their interfaces and what behaviour they have, and then use this as a starting point to develop from. In Haskell you tend to think first about the types that are involved and then work forward from there. This is a very interesting approach as it makes it possible to think about a problem in a very general and quite abstract way without getting too bogged down in detail too quickly. The types become an API to your system (rather than the interfaces, methods and domain model in an OO solution).

My experience from the course was that this tends to lead to many more types and type aliases in Haskell than I would typically define in Java or Scala. However, this soon proves to be a huge advantage as it then makes it much easier to reason about what each function does/should do and makes its behaviour very clear via the type signature. I will certainly be looking at following this practice in any Haskell programs I write and also trying to introduce more types into my Scala code.

It's Pattern Matching and Recursion All The Way Down

In a language like Java there is nothing like pattern matching and recursion has to be used sparingly if you want to avoid blowing up the stack and writing poorly performing code. In Scala there is much more scope for both, although writing tail recursive functions is still very important to ensure that you get the best optimisations from the compiler. In Haskell, pattern matching and recursion are the bread and butter of the language. Almost every single function tends to be a pattern match on arguments and the language supports a naturally recursive style across the board. Given the lazy semantics of Haskell and the optimisation in the runtime for recursive algorithms this is the best approach for building programs in Haskell.

One area for improvement that I can see in my Scala code is to make more use of pattern matching, especially partial functions.

Thinking Curried Helps a Lot

In the Scala world we typically only curry functions when there are very obvious places to partially apply them. More often than not we just partially apply a function using the underscore for one of its parameters. This is needed to ensure compatibility with Java and the object-oriented model. However, in Haskell every function is completely curried. There are no multi-argument functions. Everything is a single argument function that returns either a result or another function.

Initially I found that this made sense in the model that I'm used to: partially applying functions. However, once it came to defining new types as actually being functions as well I found that this started to fry my mind slightly. The conclusion that I came to is that it's best to just think of everything from a curried mindset and throughout the course things gradually became clearer. This thinking is essential to understand things like the State monad (which I'm still not 100% confident about to be totally honest).

Parametric Polymorphism is Very Useful

One of my biggest take-aways from the course was how useful and important parametric polymorphism is. As an (overly) simple example, what does a function from Int -> Int do? It could return the same number, add something to it, multiply it, factor it, modulus it, ignore the input and return a constant - the possibilities are nearly endless. However, what does a function from a -> a do? Given no other constraints it can only do one thing - return itself (this is called the identity function - id in Haskell).

The ability to define functions in this polymorphic way makes it much easier to reason about what a function might do and also to restrict what a function actually can do. This second point greatly reduces the possibility of introducing unexpected defects or creating functions that have multiple interweaved concerns. As another example, consider the function: Ord a => [a] -> [a]. What does this do? Well, it could just return the same input list, but because it takes the Ord type class as a constraint it's quite likely to be some form of sorting or filtering by order function. As the writer of this function I'm restricted to working with lists and just using equality and ordering functionality so the possibility of doing anything unexpected is greatly reduced.

Parametric Polymorphism is possible in Scala, but not quite as powerful as there aren't type classes for may common concepts (e.g. equality, ordering, numbers, functor, applicative, monoid, monad etc.). Introducing Scalaz fixes this for quite a lot of cases, but that's not to the taste of many projects and mixed Scala/Java teams may find this a step too far. However, there's certainly more scope for using parametric polymorphism in everyday Scala code and this is something I'm going to work on ove the coming weeks (expect some more blog posts).

Don't Try to Over Generalise

Something that I've seen in every language is that once developers discover the power of generalising concepts they tend to go overboard with this. Remember the time when every piece of code was a combination of seven billion design patterns? The power of Haskell's type classes and parametric polymorphism makes it very easy to see patterns that may not actually hold. I can see that it would be very easy to waste a lot of time and effort trying to make a data type fit into various different type classes or trying to spot type class patterns in your code and pull them out into generic concepts.

As with any kind of design pattern, generalisation or similar, the best approach (in any language) is to just build what you need to solve a problem and then when it becomes apparent that it either fits an existing pattern or represents a general pattern then this change can be made as part of a refactoring process.

Try to Keep Pure and I/O Code Separate

Haskell's I/O model at first seems very different, unusual and restrictive. Once you get your head around it, it makes so much sense. Separating pure code from code that talks about doing an I/O action from code that actually does the I/O makes for software that is much more easy to reason about, test and reuse. Very powerful and something I'm looking forward to exploring more during my journey into Haskell.

In the Scala world, I'm not sure about the need to go to such lengths as using an I/O Monad or similar. However, I can really see the advantage of separating pure code from code that performs I/O. Having pure functions that transform data and then wiring them together with the I/O performing functions at a higher level seems a natural way to create software that is better structured and easier to test. I'll certainly be playing with some approaches in Scala to experiment with this concept further.

Functors, Applicatives, Monoids and Monads are Nothing Special

A final observation from the course is that many people learning and talking about functional programming get a bit obsessed with concepts like Functors, Applicatives, Monoids and Monads (especially Monads). What I learnt is that most of these are just simple patterns that can be represented by one or two basic functions and a few simple rules. Nothing more to them really. Certainly nothing to get all worked up about!

Yes, there's a great deal of skill involved in knowing when to use these patterns, when to make your own code follow a pattern and so on, but that's true of any programming language or design pattern. It's called experience.

Conclusion

If you are a Scala developer who is enjoying the functional programming aspects of the language I would certainly recommend taking a look at Haskell. I found that it clarified lots of things that I thought I understood from Scala but still had some doubts about. Haskell is, in my opinion, a more elegant language than Scala and once you start using it you realise just how many hoops the Scala team had to jump through to maintain compatibility with the JVM, Java code and object-oriented features. Over the two days I learnt a lot about Haskell, a lot about functional programming and a lot about how to get even more value from Scala.

Type Classes Make For Better Software Structure

When people usually talk about type classes in languages like Haskell and Scala they tend to be thinking of highly generic concepts like Ordering or Numeric operations. However, in some recent experiments with Haskell I have found that type classes can be very useful for more concrete things. When used appropriately they can lead to more loosely coupled software that is more flexible and easier to change.

I Just Met You, This Is Crazy, Here's My Number, Call Me Function?

As an example, let's consider a telephone number. Fairly simple right, it's a string of digits?

def sendMessage(toNumber: String, theMessage: Message)

Or perhaps we should create a type alias to give us some better info and scope for change:

type TelephoneNumber = String

def sendMessage(toNumber: TelephoneNumber, theMessage: Message)

But wait, I'm trying to build a library that sends messages to telephones and I need to know much more about a telephone number than this 'stringly' typed data is able to tell me. Things like:

• Is it in international format?
• What's the country prefix code?
• Is it a mobile number or a landline number?
• What is the area code?
• Is it some premium rate number?
• and so on…

The Naive Solution

It's clear that my 'stringly' typed representation is not sufficient for this task unless I want to encode a whole load of rules about the world's telephone numbering systems into my library (believe me when I say I don't!). So, a naive approach would be to introduce a new type that holds the information in a more usable format. Something like:

case class TelephoneNumber(countryCode: String, areaCode: String, number: String, isMobile: Boolean, isLandline: Boolean, …)

Unfortunately, this approach suffers from a whole host of problems, including:

• If I build my library implementation against this class then I can't easily change implementation details without breaking the API
• If I copy from an instance of this type into an internal representation then I have a lot of duplication and extra code to test
• If a client uses this type in their domain model they are tightly coupled to my library (and also a specific version of it)
• If a client copies from their own representation into an instance of this type there is more duplication and extra code to test

A More Object-Oriented Approach

So, how do we deal with this? Well what we need to do is separate the behaviour of a telephone number from its actual data representation. In an object-oriented language we would do this by introducing an interface (or in Scala, a trait):

trait TelephoneNumber {
  def countryCode: String
  def areaCode: String
  def number: String
  def isMobile: Boolean
  def isLandline: Boolean
  // and so on...
}

Internally in my library I write all my code against this interface without any care as to how the underlying telephone number data is structured. Client applications are free to implement telephone numbers in whatever way they wish, provided they also implement the interface that exposes the behaviour that my library needs. Yay, problem solved. Or is it? There's still one problem in this object-oriented approach: somewhere in the client code there must be a class that implements the TelephoneNumber interface. This is problematical in a number of ways:

• The class hierarchy of the client domain model is still quite tightly coupled to my library
• It might not be possible to modify an existing domain model to implement the TelephoneNumber interface (no access to source code, coupling restrictions etc.)
• If the client domain represents telephone numbers as Strings then this class can be extended to implement the interface

Both of the last two points would result in needing to implement the same sort of mapping layer to copy between representations that we already said lead to duplication and extra code to test.

How Haskell Does It

So, in a purely functional language that doesn't have the concept of interfaces how do we solve this problem. Enter the Type Class. These clever little beasties provide a mechanism whereby the required behaviour is captured as a series of function definitions (with possible implementations if available). For example:

class TelephoneNumber a where
    countryCode :: a -> String
    areaCode :: a -> String
    number :: a -> String
    isMobile :: a -> Bool
    isLandline :: a -> Bool
    ...

So far this looks pretty much like our interface definition above except that each method takes an instance of type 'a' as a parameter and returns the result. However, the clever bit comes in that we can implement the type class for any type in Haskell without needing to modify that type in any way. For example, we could easily implement it for Strings:

instance TelephoneNumber String where
    countryCode s = ...
    areaCode s = ...
    ...

Or our client code could define its own telephone number data type and an implementation of the type class along side it:

data UKTelephoneNumber = ...

instance TelephoneNumber UKTelephoneNumber where
    countryCode t = ...
    ...

The final change is then that we have our library function require that something implementing the type class is provided rather than some concrete data type:

sendMessage :: (TelephoneNumber t) => t -> Message -> IO ()
sendMessage to msg = do
    ...
    let cc = countryCode t   -- call function on the type class passing the instance we have
    ...

In this Haskell solution we have neatly decoupled the behaviour that our library requires of telephone numbers from the data type used to represent them. Also, any client code of our library does not need to couple its data structures/types directly to the library. They can define and modify them in any way they like. All they need to do is keep the instance of the type class up-to-date.

And Finally, A Better Scala Solution

As I have hopefully shown, the Haskell solution to the problem is both elegant and leads to cleaner, more loosely coupled code. So can we do something similar in Scala? Well, yes we can because Scala also supports type classes. They are a bit less elegant than Haskell, but they work just fine. First, we need to change the TelephoneNumber trait into a type class:

trait TelephoneNumber[T] {
  def countryCode(t: T): String
  def areaCode(t: T): String
  def number(t: T): String
  def isMobile(t: T): Boolean
  def isLandline(t: T): Boolean
  // and so on...
}

Note that all we have done is added a type parameter and modified all the functions to take an instance of that type. Notice that it's now almost identical in structure to the Haskell equivalent. Next we need an implementation of this type class. Let's define one for String:

object TelephoneNumber {

  object StringIsATelephoneNumber extends TelephoneNumber[String] {
    def countryCode(t: String) = ...
    ...
  }

  implicit def TelephoneNumber[String] = StringIsATelephoneNumber
}

I've put the implementation inside a TelephoneNumber object. If you are defining your own types, convention is usually that the type classes go in the companion object (e.g. for a case class UkTelephoneNumber the type class implementations would be in the UkTelephoneNumber companion object). This insures that the type class instances are always in scope when the type is used.

Finally, lets update our sendMessage function to work with type classes:

def sendMessage[T : TelephoneNumber](toNumber: T, theMessage: Message) = {
  ...
  val telNo = implicitly[TelephoneNumber[T]]
  val cc = telNo countryCode toNumber
  ...
}

Note the use of the context bound symbol ':' plus the implicitly function to define the need for and access to the correct instance of the type class.

So there we have it, an elegant Scala solution the overcome all of the coupling problems inherent with the object-oriented approach of implementing a required interface. When should you use this? My opinion is anywhere that two system components communicate, where that communication can be defined in terms of behavioural functions rather than actual data and where you want to minimise the coupling between them and the leaking of types from one component to another.

Encoding State Requirements in Types

In my previous post I looked at a simple way to eliminate conditional expressions by encoding them into the Scala type system. In this follow-up post I want to look at taking this further by using the Scala type system to encode state rules. The aim, as always, is to create code that fails to compile rather than code that fails at runtime. By doing this we also reduce the number of unit tests required.

The Problem

Consider a simple shopping workflow. I collect information about a Basket, the Customer and their Payment Method. Once I have all this in place I can create a processOrder function that completes the workflow process. As a naive starting point, lets encode this as a simple domain model holding optional values:

  case class CheckoutWorkflow(basket: Option[Basket], 
                              customer: Option[Customer], 
                              paymentMethod: Option[PaymentMethod])

  object CheckoutWorkflow {
    def empty = new CheckoutWorkflow(None, None, None)
  }                             

Then we need some functions that populate the workflow:

  def processBasket(workflow: CheckoutWorkflow): CheckoutWorkflow = {
    if ( workflow.basket.isDefined )
      throw new IllegalStateException("Basket workflow step already processed")

    // Do some processing...
    workflow.copy(basket = Some(basket))
  }

  def processCustomer(workflow: CheckoutWorkflow): CheckoutWorkflow = {
    if ( workflow.customer.isDefined )
      throw new IllegalStateException("Customer workflow step already processed")

    // Do some processing...
    workflow.copy(customer = Some(customer))
  }

  def processPaymentMethod(workflow: CheckoutWorkflow): CheckoutWorkflow = {
    if ( workflow.paymentMethod.isDefined )
      throw new IllegalStateException("Payment Method workflow step already processed")

    // Do some processing...
    workflow.copy(paymentMethod = Some(paymentMethod))
  }

Note that each of the above functions has a guard condition to stop them being called multiple times for the same workflow. Each of these guard conditions would require a separate unit test to ensure that it works and to avoid regressions should it be accidentally removed in the future.

Finally, we need the method to process the order. Given our domain model above, this class needs to contain some conditional check to ensure that all the workflow requirements are satisfied before processing of the order can commence. Something like:

  def processOrder(workflow: CheckoutWorkflow) = workflow match {
    case CheckoutWorkflow(Some(basket), Some(customer), Some(paymentMethod)) => {
      // Do the order processing
    }
    case _ => throw new IllegalStateException("Workflow requirements not satisfied")
  }

None of the above is obviously ideal as there are a number of places that have the potential to error at runtime. The conditionals pollute our code with non-business logic. Also, we have to write good unit tests to ensure all the conditionals are working correctly and have not been accidentally removed. Even then, any client may call our code having not met the requirements encoded in the conditionals and they will receive a runtime error. Let's hope they unit test as thoroughly as we do! Surely we can do better than this?

A Less Than Ideal Solution

Well, we could use the approach outlined in my previous post and use domain model extensions:

  case class WorkflowWithBasket(basket: Basket)
  case class WorkflowWithBasketAndCustomer(basket: Basket, customer: Customer)
  case class WorkflowWithAllRequirements(basket: Basket, 
                                         customer: Customer, 
                                         paymentMethod: PaymentMethod)

  def processOrder(workflow: WorkflowWithAllRequirements) = {
     // Do the order processing
  }                                         

While this does allow removal of all the conditionals and associated tests, it unfortunatley also reduces the flexibility of our model quite significantly in that the order that the workflow must be processed is now encoded into the domain model. Not ideal. We'd like to keep the flexibility from the first solution but in a type safe way. Is there a way that we can encode the requirements into the type system?

Levaraging The Type System

First, lets consider what we want to achieve. Our aim to encode unsatisfied and satisfied workflow requirements and only allow methods to be called when the correct combinations are set. So, let's first encode the concept of requirements:

  trait BasketRequirement
  case object UnsatisfiedBasketRequirement extends BasketRequirement
  
  trait CustomerRequirement
  case object UnsatisfiedCustomerRequirement extends CustomerRequirement
  
  trait PaymentMethodRequirement
  case object UnsatisfiedPaymentMethodRequirements extends PaymentMethodRequirement

Here we have defined requirement traits for each of the different workflow stages. We also defined case objects to represent the unsatisfied state of each requirement. Next we need to indicate the satisfied states, which are our actual domain object classes:

  case class Basket(items: List[LineItem]) extends BasketRequirement
  case class Customer(id: String) extends CustomerRequirement
  case class PaymentMethod(paymentType: PaymentType) extends PaymentMethodRequirement

Next job is to make sure that our workflow object can represent these requirements and be strongly typed on either the satisfied or unsatisfied state. We do this by adding type bounds to each of the workflow types. This also allows us to eliminate the need for the Option types. We also define an 'unsatisfied' instance as the starting point for our workflow:

  case class CheckoutWorkflow[B <: BasketRequirement,
                              C <: CustomerRequirement,
                              PM <: PaymentMethodRequirement]
                              (basket: B, customer: C, paymentMethod: PM)

  object CheckoutWorkflow {
    val unsatisfied = CheckoutWorkflow(UnsatisfiedBasketRequirement,
                                       UnsatisfiedCustomerRequirement,
                                       UnsatisfiedPaymentMethodRequirements)
  }

Now we need the functions that actually process each individual workflow stage. Note how each one defines type bounded parameters for the things it doesn't care about. However, for the stage that it actually manipulates it requires that it is called with the Unsatisfied type and returns the Satisfied type. Thus, you can no longer call any of these methods with a workflow that already has that stage satisfied: the compiler won't allow it:

  def processBasket[C <: CustomerRequirement, PM <: PaymentMethodRequirement]
    (workflow: CheckoutWorkflow[UnsatisfiedBasketRequirement.type, C, PM]): 
      CheckoutWorkflow[Basket, C, PM] = {

    // Do some processing...
    workflow.copy(basket = basket)
  }

  def processCustomer[B <: BasketRequirement, PM <: PaymentMethodRequirement]
    (workflow: CheckoutWorkflow[B, UnsatisfiedCustomerRequirement.type, PM]): 
      CheckoutWorkflow[B, Customer, PM] = {

    // Do some processing...
    workflow.copy(customer = customer)
  }

  def processPaymentMethod[B <: BasketRequirement, C <: CustomerRequirement]
    (workflow: CheckoutWorkflow[B, C, UnsatisfiedPaymentMethodRequirements.type]): 
      CheckoutWorkflow[B, C, PaymentMethod] = {

    // Do some processing...
    workflow.copy(paymentMethod = paymentMethod)
  }

Finally, our processOrder function becomes super simple. You just can't call it any more unless it has no Unsatisfied types:

  def processOrder(workflow: CheckoutWorkflow[Basket, Customer, PaymentMethod]) = {
    // Process the order
  }

One observation that was made to me by someone (a Java dev) who looked at my initial draft of the code was that the final solution looks more complex due to all the type bounds and that there's actually more classes due to the need to define the requirement traits and the Unsatisfied state objects. However, don't forget that this solution eliminates at least four conditional blocks and associated unit tests, simplifies others and also possibly reduces the number of tests that clients need to write on their code as well. Also, there's no possibility of runtime failure. If the code compiles then we have a much higher confidence that it will work. Well worth a tiny bit more type complexity in my book.

Eliminating Conditionals Using Types

I've been at Scala eXchange for the last two days. One of the topics that came up a couple of times was how the type system can be used to encode knowledge and rules, making it possible for the compiler to enforce these rather than needing unit tests to verify them. There were questions from some about how this actually works in practice, so I thought I'd produce some blog posts to demonstrate. This first one covers the most simple case.

Eliminating Conditionals Using Types

Consider the following (highly simplified) domain model:

  case class CreditCheckResult(statusCode: String, creditLimit: Int)
  case class Customer(id: Long, name: String, creditCheckStatus: Option[CreditCheckResult])

This model indicates that a Customer may or may not have completed a credit check. However, we only want to register the customer if they have successfully passed through a credit check. The registration function therefore looks something like:

  def register(customer: Customer): Either[String, String] = customer.creditCheckStatus match {
    case None => Left("Attempt to register non-credit checked customer")
    case Some(ccs) => {
      // Do the registration here
      Right(registrationCode)
    }
  }

This is a very common pattern in any places where an Option (or in Java a null) is used to indicate some conditional state (rather than a truly optional piece of data). The result is that we now need a unit test for both conditional cases:

  class RegistrationSpec extends Specification {

    "The registration process" should {
 
      "register a credit checked customer" in {
        // Test code here
      }
   
      "fail to register a non-credit checked customer" in {
        register(Customer(1L, "Test")) must_== Left("Attempt to register non-credit checked customer")
      }
    }
  }

However, we can use the type system to completely remove the need for this conditional check and thus remove an entire unit test case from our code base. How do we do this? By representing the different states that a customer can be in with different types:

  case class CreditCheckResult(statusCode: String, creditLimit: Int)

  trait Customer {
    def id: Long
    def name: String
}

  case class UncheckedCustomer(id: Long, name: String) extends Customer
  case class CreditCheckedCustomer(id: Long, name: String, creditCheckStatus: CreditCheckResult) extends Customer

Our registration method can now be greatly simplified:

  def register(customer: CreditCheckedCustomer) = {
    // Do the registration here
  }

And our test now needs to cover only the valid registration case:

  class RegistrationSpec extends Specification {

    "The registration process" should {
 
      "register a credit checked customer" in {
        // Test code here
      }
    }
  }

Aaaahaaa, I hear you cry, but doesn't the complexity instead move to the creation of the correct type of Customer? In some cases this might be true, but you could easily validate this by constructing customers using this code as part of the above test. Hopefully you will be using a functional programming style and you will already have a function somewhere that takes an UncheckedCustomer and transforms them into a CreditCheckedCustomer as part of the credit check process: which will already by type safe and tested!

I'll add some more examples of using types to reduce code and unit testing over the coming week or two.

Is Scala Like EJB2?

In this post and then in this followup, Stephen Colebourne (@jodastephen) states his criticisms of the Scala language and how it feels to him similar to the same feeling of when he was working with EJB2. A colleague of mine also tweeted the following:

"This is why I will never use Scala: def ++ [B >: A, That] (that: TraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]) : That"

Here's my thoughts and experience with the above.

I started out as a C and C++ developer, but joined the Java set right at the very beginning. I've been fortunate enough to have been working in Java since 1998. Or unfortunate, if you include the early days of the Servlet API & JSP, EJB1 and then EJB2! About 2007 I really started to feel the need for a different language, one that would allow me to express my ideas more concisely and without writing so much boilerplate code. I looked at Groovy, but found it too easy to keep dropping back and writing Java. I then learned Ruby. This taught me how expressive a good language can be and how powerful closures can be. I dabbled with a few more languages before finally finding Scala at the beginning of 2009. These days I mostly code a mix of Scala, Java and Groovy. Next challenge is Clojure.

Changing Mindset

Now, I'm an engineer at heart and my typical approach is to not only understand how to use something but also (and usually at the same time) understand how and why it works. This approach always served me well when learning languages like Java and Ruby. These languages have a fairly small surface area and a relatively simple type system. It's easy to read up on them, understand how to use them and understand exactly how they work. It's easy to look at the standard and third-party libraries and see how these work as well. For me, Scala was different and involved me making a fundamental shift in mindset about how I learned the language.

When I started out I approached Scala in the same way I did other languages: I read a book and tried to build some test applications while at the same time delving into the library and language to see how they worked. This was daunting! I can fully appreciate Stephen's position that it feels a bit like EJB2. Let's put that in context. EJB2 was a horrid mess of unnecessary complexity and complication. It aimed to simplify building enterprise apps involving persistent entities and business services, but it just added way more complexity and mind effort than it saved.

Now, back to Scala. It's a big language with a very extensive and powerful type system. If you attack trying to understand it as a whole I can see how it could be mistaken as another EJB2: there seems to be loads of complexity, a lot of which you can't see the reason for and a lot of stuff just requires so much mind effort to understand. Much of it initially seems unecessary.

It was after my initial failure to understand how the Scala language and libraries actually were built and worked that I took a step back and reconsidered my learning style. I could already see some value to the language and I wanted to explore more, but how? I then made a fundamental change in my approach. I decided that it was okay for me to start using the language without necessarily understanding exactly how all the details worked. As I used the language more I would gradually try to understand the how and why, one small step at a time.

I started learning to write Scala code. When I wanted to achieve something I researched how to do it until I was familiar with the use of a particular language feature or method. If there was some syntax, implementation detail or concept that I didn't get at that point I just noted it down as something to come back to. Now after a year or so writing Scala I look back at what I didn't initially understand and it mostly makes sense. I still occasionally encounter things that don't make total sense initially, so I just learn enough to use them and then come back later to learn the why or how. It's a system that seems to work incredibly well.

When you attack looking at and learning Scala in this more gradual way, first understanding how to use it then gradually, and incrementally, delving more deeply into the type system, you begin to realised that it's not so bad. Yes, there is complexity there, but it's not the unnecessary complexity of EJB2, it's moderate complexity that helps you be expressive, write safe code and get things done. As my knowledge of Scala has grown I've yet to find any features that I haven't been able to see the value of. It's a very well thought out language, even if it doesn't quite seems so at first.

Switching from a mindset where I have to have a full understanding or how something works before I use it to one where I'm comfortable with how to use it even if I don't know why it works was a very disconcerting change in my thinking. I'm not going to say it was an easy change to make, because it wasn't. However the effort was worth it for me because it got me using a language that I now find to be many more times more productive than Java. I think I also understand the language more deeply because I have put it to use and then come back later to understand more deeply exactly how and why it worked. I would never have got to this depth of understanding with my approach to learning other languages.

An Example

Consider the method:

  def ++ [B >: A, That] (that: TraversableOnce[B])
                        (implicit bf: CanBuildFrom[List[A], B, That]) : That

There's a lot of implementation detail in there. However, in order to use this method all I really need to understand is that it allows me to concatenate two immutable collections, returning a third immutable collection containing the elements of the other two. That's why the Scala api docs also include a use case signature for this method:

  def ++ [B](that: GenTraversableOnce[B]): List[B]

From this I understand that on a List I can concatenate anything that is GenTraversibleOnce (Scala's equivalent of a Java Iterable) and that I will get a new list returned. Initially I need understand nothing more in order to use this method. I can go away and write some pretty decent Scala code.

Some time later I learn that the >: symbol means 'same or super type of' and understand this concept. I can then refine my understanding of the method so that I now know that the collection that I want to concatenate must have elements that are the same (or a supertype) as the collection I am concatenating onto.

As I later progress and learn type classes I can see that CanBuildFrom is a type class that has a default implementation for concatenating lists. I can then take this further and create my own CanBuildFrom implementations to vary the behaviour and allow different types to be returned.

I'm first learning how to use the code, then gradually refining my understanding as my knowledge of the language grows. Trying to start out by learning exactly what the first signature meant would have been futile and frustrating.

Conclusion

If you start using Scala and you take the approach of trying to see it all, understand it all and know how and why it all works then it's a scary starting place. The size and complexity of the language (particularly its type system) can seem daunting. You could easily be confused in feeling it similar to EJB2, where reams of needless complexity just made it plain unusable.

However, by switching mindset, learning to use the language and then growing understanding of how it works over time it becomes much more manageable. As you do this you gradually realise that the perceived initial complexity is not as bad as it first seemed and that it all has great value. That initial hurdle from wanting to understand it all to being happy to understand just enough is very hard to get over, but if you do then a very powerful, concise and productive language awaits you.

The Luhny Bin Challenge

Last week Bob Lee (@crazybob), from Square, set an interesting coding challenge. All the details can be found here: http://corner.squareup.com/2011/11/luhny-bin.html. I decided this sounded like a bit of fun a set to work on a Scala implementation. I'm pleased with my final result, but also learnt something interesting along the way. My full solution is available on my github account: https://github.com/skipoleschris/luhnybin.

The challenge was an interesting one, and more difficult that initial reading would suggest. In particular, the ability to deal with overlapping card number and the need to mask them both added significantly to the difficulty of the problem.

My Algorithm

The approach I selected was fairly simple. Work through the input string until a digit character was encountered. Walk forward from there consuming digit, space of hyphen characters until either the end of the string was reached, an different character was encountered or 16 digits had been collected. Next try to mach the LUHN, first on 16 digits, then 15 and finally 14. Record an object describing the index and how many characters to mask. Repeat for the next digit character and so on. After visiting all characters in the string, apply all the masks to the input.

There were some optimisations along the way. For example, if encountering 14 or less characters then there was no chance of an overlapping card number so you could safely skip over these remaining digits after the first one had been evaluated.

My Implementation

I decided to implement in Scala as this is my language of choice at the moment. I considered both a traditional imperative approach as well as a more functional programming solution. In the end I went for a very functional implementation, based around immutable data. My main reason for this choice was because I'm working on improving my functional programming skills and I though it looked like an interesting problem to try and solve in this way.

The implementation consist of for main pieces of code. Each implements a transformation of input into output, is fairly self contained. I fell that by writing them in this way I have created code that is possible to reason about and also reuse in other scenarios. I tried for elegant code rather then optimising for the most efficient and minimal code base. I think I achieved my goals.

Conclusion

While I am very happy with my solution and had great fun building it, it was very interesting to look at other solutions that had been attempted. In particular it's quite clear that the ~900ms that I was able to active on my mid-2010 MBP was a number of times slower than the fastest solutions. The inevitable conclusion being that in some cases adopting a more mutable and imperative approach may be preferable. This is a typical example of this case, when we are in effect creating a logging filter, and speed of operation could easily be argued as more important than adhering to the principles of immutability. An interesting conclusion.

Concise, Elegant and Readable Unit Tests

Just recently I was pair programming with another developer and we were writing some unit tests for the code we were about to write (yes, we were doing real TDD!). During this exercise we came to a point where I didn't feel that the changes being made to the code met my measure of what makes a good test. As in all the best teams we had a quick discussion and decided to leave the code as it was (I save my real objections for times when it is more valuable). However, this got me thinking about what actually I was uncomfortable with, and hence the content of this post.

As a rule I like my code to have three major facets. I like it to be concise: there should be no more code than necessary and that code should be clear and understandable with minimum contextual information required to read it. It should be elegant: the code should solve the problem at hand in the cleanest and most idiomatic way. Also, it must be readable: clearly laid out, using appropriate names, following the style and conventions of the language it is written in and avoiding excessive complexity.

Now, the test in question was written in Groovy, but it could just as well be in any language as it was testing a fairly simple class that maps error information into a map that will be converted to Json. The test is:

@Test
void shouldGenerateAMapOfErrorInformation() {
    String item = "TestField"
    String message = "There was an error with the test field"
    Exception cause = new IllegalStateException()

    ErrorInfo info = new ErrorInfo()
    info.addError(item, message, cause)

    Map content = info.toJsonMap()
    assert content.errors.size() == 1
    assert content.errors[0].item == item
    assert content.errors[0].message == message
    assert content.errors[0].cause == cause.toString()
}

Now, to my mind this test is at least three lines too long - the three lines declaring variables that are then used to seed the test and in the asserts. These break my measure of conciseness by being unnecessary and adding to the amount of context needed in order to follow the test case. Also, the assertions of the map contents are less than elegant (and also not very concise), which further reduces the readability of the code. I'd much rather see this test case look more like this:

@Test
void shouldGenerateAMapOfErrorInformation() {
    ErrorInfo = new ErrorInfo()
    info.add("TestField", "There was an error with the test field", 
                 new IllegalStateException())

    Map content = info.toJsonMap()
    assert content.errors.size() == 1
    assert hasMatchingElements(contents.errors[0], 
          [ item : "TestField",
             message : "There was an error with the test field",
             cause : "class java.lang.IllegalStateException" ])
}

This test implementation is more concise. There are less lines of code and less context to keep track of. To my eye I find this much more elegant and far more readable.

"But, you've added duplication of the values used in the test", I hear you cry! That is true and it was totally intentional. Let me explain why…

Firstly, as we have already mentioned, duplicating some test values actually makes the code more concise and readable. You can look at either the test setup/execution or the assertions in isolation without needing any other context. Generally, I would agree that avoiding duplication in code is a good idea, but in cases such at this, the clarity and readability far out way the duplication of a couple of values!

Secondly, I like my tests to be very explicit about what they are expecting the result to be. For example, in the original test, we asserted that the cause string returned was the same as the result of calling toString() on the cause exception object. However, what would happen if the underlying implementation of that toString() method changed. Suddenly my code would be returning different Json and my tests would know nothing about it. This might event break my clients - not a good situation.

Thirdly, I like the intention of my code to be very clear, especially so in my tests. For example, I might create some specific, but strange, test data value to exercise a certain edge case. If I just assigned it to a variable, then it would be very easy for someone to come along, think it was an error and correct it. However, if the value was explicitly used to both configure/run the code and in the assertion then I would hope another developer might think more carefully as to my intent before making a correction in multiple places.

My final, and possibly most important reason for not using variables to both run the test and assert against is that this can mask errors. Consider the following test case:

@Test
void shouldCalculateBasketTotals() {
    Basket basket = new Basket()
    LineItem item1 = new LineItem("Some item", Price(23.88))
    LineItem item2 = new LineItem("Another item", Price(46.78))
 
    basket.add(item1)
    basket.add(item2)
 
    assert basket.vatExclusivePrice == 
                       item1.vatExclusivePrice + item2.vatExclusivePrice
    assert basket.vat == item1.vat + item2.vat
    assert basket.totalPrice == item1.price + item2.price
}

In this test, what would happen if the LineItem class had an unnoticed rounding error in its VAT calculation that was then replicated into the basket code? As we are asserting the basket values based on the fixture test data we may never notice as both sides of the assertion would report the same incorrectly rounded value. By being more explicit in our test code we not only create code that is more concise, elegant and readable but we also find more errors:

@Test
void shouldCalculateBasketTotals() {
    Basket basket = new Basket()
    LineItem item1 = new LineItem("Some item", Price(23.88))
    LineItem item2 = new LineItem("Another item", Price(46.78))
 
    basket.add(item1)
    basket.add(item2)
 
    assert basket.vatExclusivePrice == 58.88
    assert basket.vat == 11.78
    assert basket.totalPrice == 70.66
}

Finally, a couple more points that people might raise and my answers to them (just for completeness!):

Q: Can't we move the constant variables up to the class level and initialise them in a setup to keep the tests methods concise?
A: This makes an individual method contain less lines of code but fails my consiseness test as there is context outside of the test method that is required to understand what it does. You actually have to go and look elsewhere to find out what values your test is executing against. This is also less readable!

Q: Isn't is better to share test fixtures across test methods in order to keep the test class as a whole more concise?
A: This might be appropriate for some facets, such as any mocks that are used in the test or if there is a particularly large data set required for the test which is not part of the direct subject of the test. However, I'd rather see slightly longer individual test methods that are explicit in their test data and assertions, even if this means some duplication or a slightly longer overall test class.

Type Classes and Bounds in Scala

I've been doing some initial experiments with the Scalaz library (https://github.com/scalaz/). This is a great extension to the Scala standard library that adds a wide range of functional programming concepts to the language. Many of its features are based around the concept of Type Classes.

The type class concept originally comes from Haskell, and provides a way to define that a particular type supports a certain behavioural concept without the type having to explicitly know about it. For example, a type class may define a generic 'Ordered' contract and implementations can be defined for different types separate from the definition of those types. Any type that has an implementation of the 'Ordered' type class can then be used in any functions that work with ordering.

The Scala language provides a way to support type classes via its implicit mechanism. In order to get my head around this fully I created some examples to experiment with how this works. Now I fully grasp the mechanisms, the Scalaz library makes much more sense. I therefore thought I'd share my experiment in case it proves useful to anyone and as an aide-mémoire to myself for the future.

In addition, my examples also make use of the different type bounds mechanisms provided by Scala, so I will demonstrate these in my examples as well.

The full source code can be found in the following gist: https://gist.github.com/1247752.

Without Type Classes

In the first example, I built a simple solution that doesn't make any use of the type class concept. This solution is much like you would implement in Java, with an interface defining the behaviour and classes that implement this interface:

trait Publishable {  
  def asWebMarkup: String
}

case class BlogPost(title: String, text: String) extends Publishable {
  def asWebMarkup =
    """|
%s
       |
%s
""".stripMargin format(title, text)
}

Here we have a trait Publishable that indicates that something can represent itself as a web markup string. Then we have a case class that implements the trait and provides the method to return the markup. Next, we declare a class that can do the publishing:

class WebPublisher[T <: Publishable] {
  def publish(p: T) = println(p.asWebMarkup)
}

Note that we have defined this as a templates class and that we have used the <: bounds notation to require that our type T is only valid if it extends the Publishable trait. All we need to do now is use it:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

Ok, so that works fine. However, what happens when we either can't or don't want BlogPost to implement the Publishable trait? There can be many reasons for this: perhaps we don't have the BlogPost domain object source; perhaps the object is already quite complex and we don't want to pollute it with publishing knowledge; perhaps it's shared by multiple teams or projects and only ours needs publishing knowledge. So, what do we do?

Without type classes there are some options: we might extends the domain class to implement the trait; we might create a wrapper class or we might create a helper utility. However, all of these result in a level of indirection and complication in our code. Let me explain...

If we internalise the knowledge of the wrapper/helper/sub-class in our publishing code we end up with some horrific type matching:

class WebPublisher {
  def publish(p: AnyRef) = p match {
    case blogPost: BlogPost => BlogPostPublishHelper.publish(blogPost)
    case _ => …
  }
}

However, if we externalise the knowledge of publishing then our client code has to do the conversion:

class WebPublisher {
  def publish(p: Publishable) = ...
}

web publish(new PublishableBlogPostWrapper(blogPost))

Clearly, both solutions lead to fragile boilerplate code that pollutes our main application logic. Type classes provide a mechanism for isolating and reducing this boilerplate so that it is largely invisible to both sides of the contract.

Type Classes with Implicit Views

Fortunately, Scala provides a mechanism whereby we can declare an implicit conversion between our BlogPost and a Publishable version of our instance. So, let's start with the simple stuff:

trait Publishable {
  def asWebMarkup: String
}

case class BlogPost(title: String, text: String) 

So, we now have a blog post that doesn't implement the Publishable trait. Let's now define the conversion that can implicitly turn our blog post into something that supports publishing (we would typically add this into our publishing code rather than the domain object in order to isolate all knowledge of Publishable to just the area that needs it):

implicit def BlogPostToPublishable(blogPost: BlogPost) = new Publishable {
  def asWebMarkup =
    """|
%s
       |
%s
""".stripMargin format(blogPost title, blogPost text)
}

Our conversion just creates a new Publishable instance that wraps our blog post and implements the required methods. But, how do we make use of this? We have to change our web publisher very slightly:

class WebPublisher[T <% Publishable] {  
  def publish(p: T) = println(p.asWebMarkup)
}

All we have in fact changed is the <: bounds to a <% bounds. This new one is called a view bounds and defines that we can instantiate a WebPublisher with type T only if there is a view (in this case as implicit conversion) in scope from T to Publishable.

Our code to call this remains the same:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

Fantastic, our publish code gets objects that it knows are publishable, while our client code can just pass domain objects. We have all the boilerplate for conversion separated out from the main code.

However, while this all seems good, this approach does have its downsides. As you can see we are using the wrapper approach: creating a new instance of a Publishable class that wraps the original object. In a high volume system, the additional object allocations of new Publishable wrapper instances on each call to the publish method may have some less than ideal memory and garbage collection impacts.

The other problem with this approach is that is reduces our ability to compose methods in interesting ways. The reason for this is that once the publishing code has actually invoked the implicit conversion it now has the Publishable wrapper rather than the original object. If it passes this Publishable to other methods or classes than these are not aware of the original wrapped type or instance.

We can overcome this problem by modifying the Publishable trait to have a generic parameter type and support a get method to extract the wrapped value - but this then should really be called PublishableWrapper and some of the simplicity starts to break down.

I think the root of the problem here is that type classes are a very functional concept and implicit views tries to coerce these into a hybrid object/functional world. Fortunately, as of Scala 2.8 there is an additional way to implement the type class approach that leads to a more functional style of coding...

Type Classes with Implicit Contexts

An alternative to implicitly converting one class to a wrapper version of that class that adds additional behaviour is to follow more of a helper like approach. In this model we provide an implicit evidence parameter that implements the type class specific behaviour. This is a much more functional approach in that we don't alter the type we are working on. So, on with the code...

trait Publishable[T] {     
  def asWebMarkup(p: T): String
}

case class BlogPost(title: String, text: String)

This is our new Publishable trait and BlogPost class. Note that our Publishable is no longer intended to be implemented or used as a wrapper. Instead, it is now a contract definition of functional behaviour that takes a parameter of type T and transforms it into a String. A much cleaner abstraction. In fact, we can even create a single object instance that implements this behaviour for blog posts:

object BlogPostPublisher extends Publishable[BlogPost] {     
  def asWebMarkup(p: BlogPost) =
     """|
%s
        |
%s
""".stripMargin format(p title, p text)
}

We are also going to need our implicit. This time however, rather than being a conversion it becomes an evidence that we have something that implements Publishable for the type BlogPost:

implicit def Publishable[BlogPost] = BlogPostPublisher 

We also need to update our WebPublisher a bit:

class WebPublisher[T: Publishable] {  
  def publish(p: T) = println(implicitly[Publishable[T]] asWebMarkup(p))
}

There are two interesting things about this class. First, the bounds has now switched from view (<%) to context (:). The context bounds effectively modifies the class declaration to be:

class WebPublisher[T](implicit evidence$1: Publishable[T]) {  ...
}

The second change is the use of implicitly[Publishable[T]] which is a convenience for getting the implicit evidence of the correct type so that you can call methods on it.

Our code to call this remains exactly the same:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

One advantage that should be immediately obvious is that we are no longer creating new instances for each implicit use. Instead, we are using the implicit evident parameter (which is in this case an object) and passing our instance to it. This is more efficient in terms of allocations.

Also, we explicitly show where we make use of the implicit evidence, which is clearer. This also means that we are never creating a new wrapped type of T that we pass on to other code. We always pass on instances of type T that have implicit evidence parameters that allow T to behave as a particular type class instance.

Conclusion

We have looked at two different approaches to solving the problem of adding behaviour to an existing class without requiring it to explicitly implement a particular contract or extend a specific base class. Both of these make use of Scala implicits and type classes.

Implicit conversions with view bounds provides an approach where a type T can be converted into the type required by the type class. This works, but there are issues associated with the wrapping or transformation aspects of the conversion.

Implicit evidence parameters within context bounds overcome these problems and provide a far more functional approach to solving the same problem.

Learnings From A Scala Project

I’ve recently been working as an associate for Equal Experts. I’ve been part of a successful project to build a digital marketing back-end solution. The project started out life as a JVM project with no particular language choice. We started out with Java and some Groovy. However, the nature of the domain was one that leant itself to functional transformations of data so we started pulling in some Scala code. In the end we were fully implementing in Scala. This post describes the learning gained on this project.

The Project

The project team consisted of five experienced, full-time developers and one part-time developer/scrum master. One of the developers (me) was proficient in Scala development (18 months, part-time) while the others were all new to the language.

The initial project configuration (sprint zero) was based on a previous Java/Groovy project undertaken by Equal Experts. The initial tooling, build and library stack was taken directly from this project with some examples moved from Groovy to Scala. The initial project stack included:

• Gradle (groovy based build system) with the Scala plugin bolted in
• IntelliJ IDEA with the Scala plugin
• Jersey for RESTful web service support
• Jackson for Json/Domain Object mapping
• Spring Framework
• MongoDB with the Java driver

Tooling

The biggest hurdle faced by the project was tooling, specifically tool support for the Scala language. While Scala tooling has come on a huge amount over the last year, it is still far from perfect. The project faced two specific challenges: build tool support and IDE support.

Build Tool Support

The Gradle build tool is primarily a build tool for Java and Groovy. It supports Scala via a plugin. Similar plugins exist for other build tools like Maven and Buildr.

What we experienced on this project was that this was not the ideal scenario for building Scala projects. Build times for loading the Scala compiler were rather slow and support for incremental compilation was not always as good as we would have liked. More often than not we just had to undertake a clean and build each time. This really slowed down test-driven development.

Currently (in my opinion) the only really workable build solution for Scala is the Simple Build Tool, also known as SBT (https://github.com/harrah/xsbt/wiki). This is a Scala specific build tool and has great support for fast and incremental Scala compilation plus incremental testing.

With hindsight it would probably have been better to switch over from Gradle to SBT as soon as the decision was made to use Scala for the primary implementation language.

IDE Support

The Scala plugin for IntellJ IDEA is one of the best editors for Scala. In particular its code analysis and highlighting has come on in leaps and bounds over the last few months. However, the support for compilation and running tests within the IDE is still less than ideal. Even on core i7 laptops we were experiencing long build times due to slow compiler startup. Using the Fast Scala Compiler (FSC) made a difference, but we found it somewhat unstable.

What was more annoying was that after failed compilations in IDEA, we often found that incremental compilation would no longer work and that a full rebuild of the project was required. This was VERY slow and really hampered development.

One proven way of doing Scala development within IDEA is to use the SBT plugin and run the compilation and tests within SBT inside an IDEA window. This has proven very successful on other Scala projects I have been involved with and again with hindsight we should have investigated this further.

Some developers on the team also found the lack of refactoring options, in IDEA, when working with Scala somewhat limiting. This is a major challenge for the IDE vendors given the nature of the language and its ability to nest function and method definitions and support implicits. Personally this doesn’t bother me quite as much as my early days were spent writing C and C++ code in vi!

Libraries

Scala has excellent integration with the JVM and can make good use of the extensive range of Java libraries and frameworks. However, what we experienced in a number of cases was that integrating with Java libraries required us to implement more code than we would have liked to bridge between the Java and Scala world. Also, much of this code was less than idiomatic Scala.

What we found as the project progressed was that it became increasingly useful to switch out the Java libraries and replace them with Scala written alternatives. For example, very early we stopped using the MongoDB Java driver and introduced the Scala driver, called Casbah. Then we added the Salat library for mapping Scala case classes to and from MongoDB. This greatly simplified our persistence layer and allowed us to use much less and more idiomatic Scala code.

Aside: If you are working with MongoDB then I strongly recommend Scala. The excellent work by Brendan McAdams of 10gen and the team at Novus has created a set of Scala libraries for MongoDB that I think are unrivaled in any other language. The power of these libraries, while maintaining simplicity and ease of use, is amazing.

We never got a chance to swap out some of the other major libraries that the original project structure was built on. However with more hindsight we should perhaps have made the effort to make these swaps as they would have resulted in much less and much cleaner code. Some specific swaps that we could have done:

• Jersey for Unfiltered or Bowler
• Jackson for sjson or lift-json
• Spring for just plain Scala code

Scala projects work well with Java libraries. However when a project is being fully implemented in Scala then it’s much better to swap these Java libraries for their Scala implemented alternatives. This results in much less and more idiomatic Scala code being required.

Team Members

Having highly experienced team members makes a big difference on any project and this one was no exception. The other big advantage on this project was that all of the developers were skilled in multiple languages, even though most had not known Scala before. One thing I have found over many years is that developers who know multiple languages can learn new ones much more easily than those who only know one. I’d certainly recommend recruiting polygot developers for new Scala projects.

It also helped having at least one experienced Scala developer on the team. The knowledge of the Scala eco-system was helpful as was the ability to more quickly solve any challenging Scala type errors. However, the main benefit was knowledge transfer. All of the team members learned the Scala language, libraries and techniques much more quickly by pairing with someone experienced in the language.

Additionally, as the experienced Scala developer I found it very valuable working with good developers who were still learning the language. I found that explaining concepts really clarified my understanding of the language and how to pass this on to others. This will be of great benefit for future projects.

Any new project that is planning on using Scala should always bring on at least one developer who already has experience in the language. It creates a better product and helps the rest of the team become proficient in the language much more quickly.

Object-Oriented/Functional Mix

We found Scala’s ability to mix both object-oriented and functional approaches very valuable. All team members came from an object-oriented background and some also had experience with functional approaches. Initially development started mainly using object-oriented techniques, but leaning towards immutable data wherever possible.

Functional approaches were then introduced gradually where this was really obvious, such as implementing transformations across diverse data sets using map and filter functions. As the team got more familiar with the functional programming techniques more functionality was refactored into functional style code. We found this made the code smaller, easier to test and more reliable.

Perhaps the only real disadvantage of moving to more functional leaning Scala code is that some code became less readable for external developer with less exposure to the functional style. It became necessary to explain some of the approaches taken to external developers: something that would probably have not been necessary with more procedural style code. This is worth bearing in mind for projects were there will be a handover to a team not skilled in Scala and functional programming techniques.

Conclusions

The project was very successful. We delivered on time and more features than the customer originally expected. I don’t think we would have achieved this if the implementation was in Java, so from that point the smaller, more functional code base produced by developing in Scala was a real winner. Using Scala with MongoDB was a major benefit. Tools was the real let-down on the project. Some problems could be alleviated by moving from Java libraries and solutions to their Scala equivalents. However, there is still some way to go before Scala tools (expecially IDEs) match the speed an power of their Java equivalents.

Thought For The Day: Programmers

A BAD programmer...

...writes loads of code that usually doesn't work. When they do get it to work they have no idea why it does so [programming by coincidence].

An AVERAGE programmer...

...writes loads of code that works. They are happy that it is working and they broadly understand why it does.

A GOOD programmer...

...implements the same working functionality as the average programmer, but they use far less (and more simple) code to do so. As their code is smaller and simpler, they fully understand why it works.

An OUTSTANDING programmer...

...writes the same code as the good programmer but then refactors until most of it gone. What remains is clean an elegant. Their code is so good that even the bad programmer can understand it.

Cleaner Code with the Scala Type System

Last week I happened to be sitting with a colleague looking at some prototype Java code. We came across a method that neither of us was particularly happy with, but which represented the typical messy code that occurs when wanting to do anything involving types and classes in Java. My initial comment was that it "would be so much cleaner to do in Scala". I therefore thought I'd better have play with the code to prove (if only to myself) that I was right. This post discusses the result of my effort and my conclusions from having done this work.

The Problem

In order to understand the code, let's first look at the problem that it is tying to solve:

The domain is one related to content that can appear on a website. We have a persistent domain model representing this content. However, a number of the content items are sourced from and can be updated in external systems (e.g. a CMS system or a remote content provider). We therefore need to synchronise the state of these external systems into our domain model from time to time. The java code that we were looking at was inside this synchronisation component.

The content is retrieved from the external systems, wrapped in a subtype of ForeignObject. The subtype is based on where the content was obtained from. The ForeignObject implementations can examine the content they contain and return information about its type and its unique business identifier. The synchronisation code then uses this information to lookup the associated object in the persisted domain (which may or may not exist). The ForeignObject and domain object are then passed to a mapper that updates the domain object from data that it extracts from the ForeignObject instance.

The full source code and tests described below can be obtained from my Github account: http://github.com/skipoleschris/type-safe-sync.

The Java Code

Let's first take a look at the Java code that we were less than happy about. Firstly, the ForeignObject implementation that returns the detail about the type of content that it contains:

public class CMSForeignObject implements ForeignObject {
     // Other code removed

    @Override
    public Class getLocalClass() {
        if ("Story".equals(type)) return Story.class;
        else if ("Image".equals(type)) return Image.class;
        else if ("BinaryObject".equals(type)) return BinaryObject.class;
        else if ("RelatedLinks".equals(type)) return RelatedLinks.class;
        else throw new IllegalStateException("Unknown type: " + type);
    }
}

As we can see it looks at some string based type field that it extracts from the wrapped content and returns the associated domain class that represents that content. Perhaps not the nicest code and returning class instances always feels a bit wrong. However, I don't have too many problems with this approach. Where the messy code comes in is in the synchronisation logic that uses this class:

public class SynchronisationService {
     // Setup code remove for clarity

    @SuppressWarnings( { "unchecked" })
    public Content sync(final ForeignObject foreignObject) {
        return findById(foreignObject.getLocalClass(), foreignObject);
    }

    @SuppressWarnings("unchecked")
    private  T findById(final Class clazz, final ForeignObject foreignObject) {
        if(Story.class.equals(clazz)) {
            CMSForeignObject cmsForeignObject = (CMSForeignObject)foreignObject;
            return (T)repository.findStoryById(cmsForeignObject.getId());
        }
        else if(Image.class.equals(clazz)) {
            CMSForeignObject cmsForeignObject = (CMSForeignObject)foreignObject;
            return (T)repository.findImageById(cmsForeignObject.getId());
        }
        else if(BinaryObject.class.equals(clazz)) {
            CMSForeignObject cmsForeignObject = (CMSForeignObject)foreignObject;
            return (T)repository.findBinaryObjectById(cmsForeignObject.getId());
        }
        else {
            throw new IllegalStateException(
                "We have managed to try and synchronise an unsupported class. This is a bug.");
        }
    }
}

How's that for a nice bit of logic? Imagine when we have many different types! I know this is only prototype code and there's certainly plenty we can do to improve it. However, it's quite typical to see this sort of stuff in production code whenever you have to go down into type based logic in Java.

The First Scala Version

To come up with a better solution, the first thing I did was to just convert the Java code directly into Scala. Nothing special here, other than using Scala syntax and modifying to return Option[Story] rather than null. So, first the ForeignObject implementation:

class CMSForeignObject(typeName: String, val id: String) extends ForeignObject {
  def localClass[C <: Content]() = typeName match {
    case "Story" => classOf[Story]
    case "Image" => classOf[Image]
    case "BinaryObject" => classOf[BinaryObject]
    case "RelatedLinks" => classOf[RelatedLinks]
    case _ => throw new IllegalStateException("Unknown type: " + typeName)
  }
}

And the synchronisation code:

class SynchronisationService(repository: ContentRepository) {

  def sync(foreignObject: ForeignObject): Option[Content] = findById(foreignObject.localClass, foreignObject)

  private def findById[T <: Content](clazz: Class[_], foreignObject: ForeignObject) = {
    if ( clazz == classOf[Story] )
      repository.findStoryById(foreignObject.asInstanceOf[CMSForeignObject].id).asInstanceOf[Option[T]]
    else if ( clazz == classOf[Image] )
      repository.findImageById(foreignObject.asInstanceOf[CMSForeignObject].id).asInstanceOf[Option[T]]
    else if ( clazz == classOf[BinaryObject] )
      repository.findBinaryObjectById(foreignObject.asInstanceOf[CMSForeignObject].id).asInstanceOf[Option[T]]
    else throw new IllegalStateException("We have managed to try and synchronise an unsupported class. This is a bug.");
  }
}

Works fine, but not really much better than the Java code.

Adding Scala Type Goodness

Once I had an initial Scala version I then spent a couple of hours playing around with the code and some Scala type goodness. The resulting synchronisation code is:

class SynchronisationService(repository: ContentRepository) extends ContentFinder {

  def sync(foreignObject: ForeignObject): Option[Content] = findById(foreignObject)

  private def findById[C <: Content, FO <: ForeignObject](foreignObject: FO) =
    Option(finder(findStory) orElse finder(findImage) orElse 
           finder(findBinaryObject) apply foreignObject)

  private def findStory(foreignObject: CMSForeignObject) = repository findStoryById (foreignObject id)
  private def findImage(foreignObject: CMSForeignObject) = repository findImageById (foreignObject id)
  private def findBinaryObject(foreignObject: CMSForeignObject) = repository findBinaryObjectById (foreignObject id)

No nasty if/else block. No need to deal with Class instances. No nasty type casting. Much more readable. Hopefully this is much more friendly for developers and will be far easier to maintain in the future as we come to add more types of content to be synchronised. So, how did I manage to achieve this much more readable code?

The first piece of the puzzle was to eliminate the returning of Class instances from the ForeignObject. Instead we now return a new ContentType instance:

class CMSForeignObject(typeName: String, val id: String) extends ForeignObject {

  def contentType[C <: Content, FO <: ForeignObject] = {
    val contentType = typeName match {
      case "Story" => new ContentType[Story, CMSForeignObject]
      case "Image" => new ContentType[Image, CMSForeignObject]
      case "BinaryObject" => new ContentType[BinaryObject, CMSForeignObject]
      case "RelatedLinks" => new ContentType[RelatedLinks, CMSForeignObject]
      case _ => throw new IllegalStateException("Unknown type: " + typeName)
    }
    contentType.asInstanceOf[ContentType[C, FO]]
  }
}

The ContentType instance supports generics on both the type of content and the type of foreign object. It captures the actual erased types used via implicit manifests on its constructor:

class ContentType[C <: Content, FO <: ForeignObject]
        (implicit val mC: Manifest[C], val mFO: Manifest[FO]) {

  def compatibleWith(cClass: Class[_], foClass: Class[_]) = (cClass == mC.erasure) && (foClass == mFO.erasure)
}

It also provides a compatibleWith method that is used internally within the finder code that we will look at below.

This final piece of the puzzle is the implementation of theContentFinder trait that is mixed in to the synchronisation code. This is where most of the type magic occurs in order to simplify the actual synchronisation code:

trait ContentFinder {
  implicit protected def finderToPartialFunction[FO <: ForeignObject, C]
        (handler: LookupHandler[FO, C])(implicit mFO: Manifest[FO], mC: Manifest[C]) =
    new PartialFunction[AnyRef, C] {
      def apply(foreignObject: AnyRef) =
        if ( isDefinedAt(foreignObject) ) handler(foreignObject.asInstanceOf[FO])
        else throw new IllegalStateException("We have managed to try and synchronise an unsupported class. This is a bug.")

      def isDefinedAt(foreignObject: AnyRef) =
        foreignObject.asInstanceOf[FO].contentType.compatibleWith(mC.erasure, mFO.erasure)
    }

  protected def finder[FO <: ForeignObject, C](lookup: FO => Option[C]) = new LookupHandler(lookup)

  protected class LookupHandler[FO <: ForeignObject, C](lookup: FO => Option[C]) {
    def apply(foreignObject: FO) = lookup (foreignObject).getOrElse(null).asInstanceOf[C]
  }
}

The first insight that I had when working with this code is that the if/else condition across classes is actually a partial function across content types. We have a ForeignObject that can return a ContentType instance that contains the type information about the type of content and the type of foreign object. We therefore just have to see if there is a partial function defined at that particular combination and if there is then we can apply it.

The resulting implementation therefore defines a finder method that takes a function containing the actual code that should be applied to the ForeignObject/Content pair. It returns this wrapped in a LookupHandler instance. The synchronisation code can then just define find functions for each type that it can deal with and pass them to the finder method. Finally we define an implicit conversion for the LookupHandler instances that convert them to partial functions so that we can compose them with the orElse method. The partial function captures the erased types from the handler using implicit manifests and compares these with those captured by the content type to see if the function can be applied.

Conclusion

We can clearly see that the resulting synchronisation code is significantly cleaner, more easily understood and more maintainable than the original Java code. However, this comes at the expense of slightly more lines of Scala code and some fancy logic around finders and implicit partial functions. Is the benefit really worth the extra?

I can see both sides of the argument. I can certainly understand that for the Scala novice that the ContentFinder is somewhat impenetrable. However, its the synchronisation code that is likely to be updated a number of times as more types of content are bought into the domain. The code to deal with all of the type goodness is unlikely to change that much and can be easily maintained by more experienced Scala developer. Therefore the readability and maintainability of the business code wins out in my mind over some extra, well abstracted complexity.

This tends to be the typical approach to the Scala language and one of the reasons that it can be so incredibly powerful. Use all the power of the language and its incredible type system in the framework and support code so that the actual application logic can be as minimal and simple as possible.

Functional Programming Challenge: Most Frequent Multiple Occurring List Item - SOLUTIONS

In this post I set out a challenge to come up with the best solution to the following problem: how to find the most frequently multiple occurring item in a list.

I had created my own solution, but felt that a better one was possible. The criteria specified were simple code, elegance and performance.

I have had two submissions to the problem so far and this post offers a comparison of them along with my original solution. My comparisons were carried out using the following two test lists:

val random = new java.util.Random(2L)
val list1 = (for ( i <- 1 to 100000 ) yield random.nextInt).toList.distinct
val list2 = (for ( i <- 1 to 100000 ) yield random.nextInt(1000)).toList

The first list contains no duplicate elements, so the result should always be None. The second list will contain multiple duplicate elements.

My Solution

My solution to the problem was based around building a map of list items to frequency count and then finding the most frequent multiply occurring item in that map. My implementation was achieved with two small functions and two foldLeft operations:

def highestMultipleFrequency1[T](items: List[T]): Option[T] = {
  type Frequencies = Map[T, Int]
  type Frequency = Pair[T, Int]

  def freq(acc: Frequencies, item: T) = acc.contains(item) match {
    case true => acc + Pair(item, acc(item) + 1)
    case _ => acc + Pair(item, 1)
  }
  def mostFrequent(minOccurs: Int)(acc: Option[Frequency], item: Frequency) = acc match {
    case None if item._2 >= minOccurs => Some(item)
    case Some((value, count)) if item._2 > count => Some(item)
    case _ => acc
  }
  items.foldLeft(Map[T, Int]())(freq).foldLeft[Option[Frequency]](None)(mostFrequent(2)) match {
    case Some((value, count)) => Some(value)
    case _ => None
  }
}

In the tests, my solution performs fairly consistently across both test lists, the second being slightly faster due to the smaller size of the map being used by the second fold function.

Solution from Nilanjan R

This solution send by Nilanjan R is significantly simpler and shorter in the amount of code it uses. It takes the approach of grouping items by themselves and then sorting the resulting lists by their size and taking the first item:

def highestMultipleFrequency2[T](items: List[T]): Option[T] = {
  items.groupBy(x => x).values.toList.sortWith((f, s) => f.size > s.size) match {
    case x :: xs if x.size >= 2 => Some(x.head)
    case _ => None
  }
}

Under test, this solution performs significantly slower than my solution on the list without duplicates. However, when the list does contain significant multiple occurring elements then it performs slightly better than my solution. To me this tends to indicate that the sort function is the major performance factor in this solution. I do really like this due to its very clean, simple and easy to understand code. It's certainly my choice for the Noughts and Crosses application where simple code is more important than raw performance and where I am only dealing with very small lists.

Solution from Antonin Brettsnajdr

The solution offered by Antonin follows a similar approach to my solution in that it builds a map of item frequencies and then find the most frequently occurring element using this map. However, this solution implements the whole algorithm in a single tail-recursive function:

def highestMultipleFrequency3[T](items: List[T]): Option[T] = {
  def mff(l: List[T], m: Map[T, Int]): Option[T] = l match {
    case element :: tail => if (m contains element) mff(tail, m.updated(element, m(element) + 1))
                            else mff(tail, m + (element -> 1))
    case Nil => val occurences = (m map { item => item._2 }) 
                if (occurences forall (_ == 1)) None 
                else {
                  val maxOccur = occurences.max
                  m find ( letter => letter._2 == maxOccur) match {
                    case Some(x) => Option(x._1)
                    case None => None
                  }
                }
  }
  mff(items, Map())
}

This solution is by far the best performing. It is two to three times faster than my solution. There is a significant performance benefit when dealing with a list that contains multiple duplicated items. While the code is not as simple as the previous solution, it is very readable and is a nice example of tail recursion.

A big thanks to Nilanjan R and Antonin Brettsnajdr for their solutions. I found it very interesting looking at the different way people approach a problem such as this. Can you do better? Let me know your solution.

Functional Programming Challenge: Most Frequent Multiple Occurring List Item

A little functional programming challenge for those who like that sort of thing. This one came up while I was improving my Noughts and Crosses example application.

The challenge is this: Given a list of elements of type T, find the element with the most multiple occurrences.

For example, the following should apply:

List("a", "b", "c", "a", "b", "a") 
    -> should return "a" as this occurs the most in the list
List("a", "b", "c")                
    -> should return nothing as no elements occur multiple times
List("a", "b", "a", "b")           
    -> can return either "a" or "b" as they both occur the same number of times

The simplest solution I have come up with so far (written in Scala) is:

def highestMultipleFrequency[T](items: List[T]): Option[T] = {
  def freq(acc: Map[T, Int], item: T) = acc.contains(item) match {
    case true => acc + Pair(item, acc(item) + 1)
    case _ => acc + Pair(item, 1)
  }
  def mostFrequent(frequencies: Map[T, Int], minCount: Int = 2) = {
    frequencies.find(_._2 == frequencies.values.max) match {
      case Some((value, count)) if count >= minCount => Some(value)
      case _ => None
    }
  }
  mostFrequent(items.foldLeft(Map[T, Int]())(freq))
}

While this works and is fairly elegant I can help feeling that there must be a better way. Traversing the entire list to build a map of item to frequency and then searching all the values in that map to find the one occurring the most just seems a tad clunky.

I also played around with an alternative implementation for the mostFrequent function, but I'm not sure this is any better or more efficient:

def mostFrequent(frequencies: Map[T, Int], minCount: Int = 2) = {
  frequencies.toList.map(_.swap).max match {
    case (count, value) if count >= minCount => Some(value)
    case _ => None
  }
}

Finally I came up with this solution, which requires less traversal through the map than the previous ones, even if the code is slightly longer and the generics for the foldLeft methods are less readable:

private def highestMultipleFrequency[T](items: List[T]): Option[T] = {
  type Frequencies = Map[T, Int]
  type Frequency = Pair[T, Int]

  def freq(acc: Frequencies, item: T) = acc.contains(item) match {
    case true => acc + Pair(item, acc(item) + 1)
    case _ => acc + Pair(item, 1)
  }
  def mostFrequent(acc: Option[Frequency], item: Frequency) = acc match {
    case None if item._2 >= 2 => Some(item)
    case Some((value, count)) if item._2 > count => Some(item)
    case _ => acc
  }
  items.foldLeft(Map[T, Int]())(freq).foldLeft[Option[Frequency]](None)(mostFrequent) match {
    case Some((value, count)) => Some(value)
    case _ => None
  }
}

Anyone want to offer a different (better) solution? Use the functional programming language of your choice. Points awarded for simplicity, elegance and efficiency. The winning solution will be published here and (if the provider agrees) will be put into my Noughts and Crosses example in place of the current implementation.

Simple and Elegant Property Model

In this post I talked about the need to create simple and elegant solutions to software problems rather than over engineer. I used as example a property mechanism that I have been working on for my new product. Having now got this to a state where I believe it is both simple and elegant I thought I'd share the evolution of the Scala code as a way of exploring this topic in more detail.

The goal of this particular set of classes is to provide a mechanism whereby a (super)user can define definitions for the properties that can be set against an item. The user creating the item then fills in values for these properties. Both users will be utilising a web interface for defining and setting properties. In addition properties may be mandatory and optional and can support default values.

Please note that all the code below was developed iteratively using a Test-Drive Development (TDD) approach. I'm not going to show the tests here, so please be aware that every iteration through the model was first backed by a test to define the required behaviour.

So, after my initial attempt at a solution that became far too complex and over engineered I rolled back to the simplest thing that I could possibly write:

case class PropertyDefinition(name: String)

case class Property(name: String, value: String)

object Property {
  def apply(definition: PropertyDefinition, value: String) = Property(definition.name, value)
}

This simple starting point meets the minimum requirements of a definition of a property and then a property that maps a name to a string value. While this is indeed simple, it's too simple in that it doesn't meet all the requirements and it's also not particularly elegant in the way it restricts values to be strings.

The next step was to add support for mandatory/optional functionality. The property definition was easy to change:

case class PropertyDefinition(name: String, mandatory: Boolean = false)

However, the property concept is more challenging as it is now possible to have properties with no value associated. With the general Scala goal of avoiding using null to represent no value, I instead modified property to hold and Option[String] instead:

case class Property(name: String, value: Option[String])

object Property {
  def apply(definition: PropertyDefinition, value: Option[String]) = value match {
    case None if !definition.mandatory => new Property(definition.name, None)
    case Some(_) => new Property(definition.name, value)
    case _ => throw new IllegalArgumentException("Value must be supplied for property")
  }
}

This is still a pretty simple solution. However it's still missing the requirement for default value support and it now seems less elegant because instead of creating a property with

Property(nameDefinition, "value")

I have to use

Property(nameDefinition, Some("value"))

Also, I'm still linked tightly to String value types. First I decided to deal with the default value requirement:

case class PropertyDefinition(name: String, mandatory: Boolean = false, defaultValue: Option[String] = None)

case class Property(name: String, value: Option[PropertyValue])

object Property {
  def apply(definition: PropertyDefinition, value: Option[String]) = value match {
    case None if definition.defaultValue != None => new Property(definition.name, definition.defaultValue)
    case None if !definition.mandatory => new Property(definition.name, None)
    case Some(_) => new Property(definition.name, value)
    case _ => throw new IllegalArgumentException("Value must be supplied for property")
  }
}

I now have the simplest solution that meets all my requirements. Many developers would stop at this point, but I still feed uncomfortable that the code is not particularly elegant. I don't want to over engineer additional complexity but I'd like to have a cleaner interface to the classes that I have created so far and I'd also like to leave more scope for future changes where possible.

My first improvement was to pull out the tight coupling to a String and instead introduce a PropertyValue class as a wrapper around a string:

case class PropertyValue(content: String) 

case class PropertyDefinition(name: String, mandatory: Boolean = false, defaultValue: Option[PropertyValue] = None)

case class Property(name: String, value: Option[PropertyValue])

object Property {
  def apply(definition: PropertyDefinition, value: Option[PropertyValue]) = value match {
    case None if definition.defaultValue != None => new Property(definition.name, definition.defaultValue)
    case None if !definition.mandatory => new Property(definition.name, None)
    case Some(_) => new Property(definition.name, value)
    case _ => throw new IllegalArgumentException("Value must be supplied for property")
  }
}

Now my property code is not fixed to a string, although my initial implementation of property value is still string based. This has the benefit of keeping the initial version simple but providing scope for someone to refactor the implementation of property value in the future to support different types or other requirements.

So, one element of elegance of the code is improved. Unfortunately it comes at the expense of another. To create a property you now have to type:

Property(nameDefintion, Some(PropertyValue("value"))

Yuk! I need a way to easily build an Option[PropertyValue] from a String in order to avoid all the boiler plate code. This is where Scala implicit conversions come to the rescue. I think their overuse can create code which can be very difficult to debug as you are never certain what implicit conversions are being applied. However in this case they are perfect for bringing the final level of elegance to the code:

object PropertyValue {
  implicit def wrapString(content: String) = content match {
    case "" => None
    case _ => Some(new PropertyValue(content))
  }
  implicit def unwrapString(value: Option[PropertyValue]) = value match {
    case Some(v) => v.content
    case None => ""
  }
}

Given these implicit conversions I can now type:

val property = Property(nameDefinition, "value')

val content: String = property.value

This ticks all my boxes for simplicity and elegance. The code is clean and simple; all the requirements are met. The interface to the classes is also clean and intuitive. However, the solution is also elegant in that it provides ways for future extension without adding excessive additional complexity. Future developers should be able to enhance this code to support more features (such as validation or type safe values) without having to rewrite it from scratch. Time to move on to the rest of my domain model...