Java, Programming

Splitting Loot with Scala

Over the last couple of days I have been trying to implement the Sharing Problem (Ruby Quiz #65: Splitting the Loot) in Scala. So far I have implemented the greedy pick algorithim and still need to implement a recursive solution that will brute force the edge cases.

However on the way I think I have picked up some important lessons. You can see the code for yourself in the GitHub project related to the problem and the solution (it’s in the Scala directory) but I will be highlighting some of the code in this post.

This was the first set of Scala I’ve done that was actually an attempt to use some of the functional aspects of Scala rather than just porting Java code in a more or less literal and imperative way. After struggling a little bit with the implict return and list concatenation I implemented the greedy heuristic. This is what it looked like (link to the code file).

import gems._

package splitter {

  class LootSplitter

  object LootSplitter {
    def splitLoot(gembag: GemBag, shares: Int): List[GemBag] = {

      if((gembag.totalValue % shares) != 0) {
        return List[GemBag]()
      }

      val individualShareValue = gembag.totalValue / shares

      var partShares: List[GemBag] = List.make(shares, new GemBag(List()))

      gembag.gems.sort(_.value > _.value).foreach((gem: Gem) => {
        partShares = partShares.sort(_.totalValue < _.totalValue)
        partShares = List(partShares(0) add gem) ::: (partShares drop 1)
      })

      partShares
    }

    }
  }
}

I was struck initially by how compact this code was, you are looking at about 28 lines of code. However as I was looking at it I began to wonder whether it was concise or just terse. How is someone meant to interpret something like _.value > _.value? I showed it to a collegue and his first reaction was “I don’t know functional languages so I wouldn’t know what this means”.

This was exactly the kind of reaction I was afraid of because I have been converted heavily to the principal of readable code. Someone should be able to scan code and understand, in principle, what is happening here. If they don’t then the cost of maintaining that code is going to be higher and we have actually lost something in the concise syntax.

I decided to try and implement a readable version of the same file which added about 6 lines (only two according to GitHub!). You can read this version here but now I want to throw it open to the public. Is this version actually easier to read? Are things like the underscore variable actually part of the price of comprehending Scala?

In my rewritten version I use some of the nice features of Scala such as first order functions but you still have lines like this:

List(sortedBags(0) add gem) ::: (sortedBags drop 1)

I hope you are reading this as “add a gem to the first sortedBag and make a List of it and then add all the other bags except the first one to the new list” but I am worried that this is far from obvious. Is that because I’ve done something that isn’t idiomatic or is it because actually the operators and the library API are too obscure?

Scala represents a significant evolution of Java in terms of absorbing all the lessons learned during the evolution of the language. When porting Java code I feel far more comfortable with it than when I am trying to create new code that uses the core language libraries. I don’t want to evolve to a new set of problems and best practices that try to avoid them.

Standard

6 thoughts on “Splitting Loot with Scala

  1. I find Chinese totally illegible. I can’t even reliably recognize when I see the same ideogram twice. But a lot of people, like about a billion of them, read Chinese with no problem.

    Is it surprising that a Java programmer doesn’t find Scala readable?

    _.value > _.value is so much nicer than the named param version. But an alternative is

    def ascending[A,B B) = (x:A, y:A) => f(x) <= f(y)
    def descending[A,B B) = (x:A, y:A) => f(x) >= f(y)

    List(“three”, “one”, “2Two”).sort(ascending(_.length))

  2. The Readable Code principle is meant to transcend particular languages such as Java and Scala. The intent of the code should be clear from reading the code.

    If you combine it with Domain Driven Design principle then the code should also reflect the language of the domain. Although that could sit in a DSL on top of core Scala syntax.

    This isn’t about “do dumb ol’ Java programmers understand Scala?” although that is also a relevant question.

  3. I said nothing about dumb. I don’t read Chinese, that doesn’t make me dumb. Most in China don’t read English, yet I don’t assume they’re dumb.

    Why do you think programming *languages* transcend a fundamental aspect of any other language? Readability of a particular sample depends critically on your ability to read the language first. Only after you know the language are you in a position to judge readability of a sample. Mathematicians in one speciality often can’t read notation of mathematicians in another speciality, but when reading within their discipline they can eat complex papers for breakfast.

    Look, here’s a bit of Prolog. It captures its domain perfectly, and is instantly recognizable to any Prologer

    append([],L,L).
    append([H|T],L,[H|LT]):-append(T,L,LT).

    However, the semantics of Prolog are so different from Java or Scala that of course it looks different from either one. I’d say it’s near incomprehensible to an applicative programmer.

    Scala’s semantics share a great deal with Java, but they are different languages with differing semantics. In particular Scala has first class functions and partial application.

    So my point is that it’s not much more reasonable to expect Scala code to be readable to a Java programmer than it is to expect a Scala programmer to be able to judge the readability of a bit of Prolog.

    If people who don’t speak the language had to judge the readability of English would Steinbeck have ever been published?

    It has nothing to do with dumb.

  4. I’m unconvinced by any of this. If the intent of the code cannot be inferred by reading it and that obscurity is the result of the language semantics then I’m not sure that language is really a good general purpose language. It is going to have a high entry cost and ongoing maintenance is going to be higher.

    There has to be a good reason to use symbols rather than labels. Scala does use labels with things like Some and List.foldRight/Left. I could live with the underscore but using “<-” instead of “in” seems unnecessarily obscure for example. Ditto :: and :::.

    The Chinese metaphor really isn’t working for me. Literature-wise my concern is that aspects of Scala read like Joyce and I think a workhorse language should read like Greene.

  5. open parenthesis four plus seven close parenthesis times eighteen divided by one thousand seven hundred and sixteen

    (4 + 7) * 18 / 1716

    Which would you rather read? For me, definitely the later. Because I’ve learned that language and value its conciseness.

    How ’bout this one?

    x = x + 1

    You probably don’t even wince at that a little, even though it makes no sense – how can x be the same value as x plus 1? Oh wait, that’s not equality, that’s assignment. At least in the Pascal/Delhpi line they made it x := x + 1.

    The <- in “for (x <- lst)…” at least graphically looks like what it does, unlike “=” or Java’s not-the-same-but-close-enough “:” in “for (SomeType x : lst) ….” It could have been “in”, certainly, but you know…there’s always Cobol.

    As for ::, it’s stolen from ML and if you build lists using 1::2::3::Nil it looks pretty darned nice. Be that as it may, :: and ::: aren’t part of the language. They’re part of the library.

    I couldn’t disagree more with a language reading like Joyce. The language itself allows pretty pedestrian coding. You can use it like Joyce or not.

    I can write Java in a way that makes Finnegan’s Wake look like See Spot Run.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s