Functional Programming in Scala

Richard Feynman said what I cannot create I do not understand, notoriously misquoted by Craig Venter as what I cannot build I do not understand when he inserted it as a watermark into the DNA of his bacterium with an artificial genome. But Venter has a software engineering approach to biology - the bacterium has a computer for a parent and he went through a series of debugging cycles before eventually the organism would 'boot-up'. His statement is fundamental to the proper understanding of all sorts of disciplines, but non more so than software development.

Manning have today published Functional Programming in Scala by Rúnar Bjarnason and Paul Chiusano. The book is constructed around a carefully graded sequence of exercises where you find yourself attempting to build things of increasing complexity. It's aim is to teach functional programming concepts through the medium of Scala and this means that you must construct your programs from pure functions, free of side effects.  If, like me, you come from an OO background, this causes a massive rethink - there are whole swathes of the language that you just don't use.  For example, you can't reassign a variable; your functions mustn't throw exceptions; you will not develop class hierarchies.  You will use case classes but their use is restricted to the creation of algebraic data types. I found that I had to go through the exercises very slowly and deliberately.  The introductory exercises are relatively straightforward and fun to attempt and your confidence grows, but I found that the material quite soon becomes very challenging indeed.  In fact, whilst studying the various revisions of this book, I was reminded yet again of Feynman - his algorithm:

    Write down the problem.

    Think real hard.

    Write down the solution.

This, as opposed to an approach I've tended to used in OO:

   
    Write down the problem.

    do {
        Think a little bit.

        Type a little bit.

        See what happens

    } until problem solved.

    Write down the solution.  

The problem when lesser mortals attempt Feynman's algorithm is that it tends not to terminate. When it works, however, you often tend to end up with an elegant, terse solution, often incomprehensible to the casual reader. But the main thing is that you gain enormous understanding - you will get no benefit unless you attempt the exercises.

The material is presented tersely, with just enough explanation of the concept and the scala syntax you need to express it.  Some of the problems are very tricky and I would occasionally find myself pondering single questions for an hour or two, struggling to get the types to match.  The satisfaction when you do tease out a solution is immense.  The accompanying material on the web site includes pro-forma Scala exercise files for each chapter with placeholders for the answer, usually in the fom of stubs like this:

    def compose[A,B,C](f: B => C, g: A => B): A => C =
        ??? 

If you get stuck, hints and solutions for each question are provided, as is a fully fleshed-out answer file for each chapter.  Some later chapters use material developed in earlier ones and so, when attempting a new chapter, you need either to have completed the previous ones or to compile the supplied answers before you can proceed.

There are four main sections. The first is an introduction to FP concepts and the authors have given a lot of thought to the progression of ideas.  This allows you gradually to gain confidence in manipulating functions until finally you're able to develop a lazily-evaluated Stream data type and then a purely functional representation of State. If you just get this far, it's of tremendous benefit.

Then the style of the book changes tack to some extent in three chapters devoted to functional design.  The idea is to illustrate some of the thought processes and alternative approaches that can be involved in groping your way towards the development of a combinator library that tackles a particular design space. Three completely different problems (parallelism, test frameworks and parsers) are used. This is illuminating but sometimes a little at odds with the progression of exercises because your approach and the authors' may legitimately diverge.  This means you may occasionally have to look ahead to the answers to keep yourself on track. What is interesting here is that the three different areas evolve solutions with a deep structure in common and you develop something of an intuition of what it is that makes Monads inevitable.

The third section then discusses Monoids, Monads, Functors and Applicatives.  This is familiar territory if you've read Learn You a Haskell but there is considerably more depth of coverage, and because you've spent so much time thinking about the diverse design problems in the previous section, you may well find that your understanding of these deep abstractions takes a more tangible form.

Section 4 deals with the question - if your program is completely pure, how do you deal with an effect such as IO?  There are many aspects to this and the authors review the strengths and limitations of the IO Monad and discuss different alternatives to the problem of handling mutable state. The book ends with a fascinating chapter on Streaming IO.  This was a brave thing to do - the discussion is exploratory in style and feels its way towards a thorough explanation of the design principles behind the scalaz-stream library. It seems as though the chapter might have been developed in parallel with the development of the library itself and you almost think that you are one of the team. Surprisingly, no mention is made of scalaz, however you will learn many of the design principles that underpin it.  (This won't give you everything you need for the scalaz syntax, though.  For this, I would recommend learning-scalaz.)

This is a book which has already taught me a great deal and given me a huge amount of pleasure.  It is one that I will keep going back to until I finally feel that I am getting the hang of that mysterious activity which is called functional programming.
 

Lenses in Scala

I have just got back from Scala eXchange 2013 where the initial keynote session was from Simon Peyton Jones on Lenses: Compositional data access and manipulation. A presentation in pure Haskell was, in fact, quite a heavyweight start to a Scala conference. However, it turned out to be a lucid explanation of a beautiful abstraction, and one which, at first sight, would appear to be impossible to arrive at given the apparent inconsistency of the types. Have a look at Simon's presentation if you find time - it's well worth the effort.

A lens solves the problem of reading from, and updating, a deeply nested record structure in a purely functional way, but without getting mired in ugly, deeply nested and bracketed code. Anyway, the talk got me interested in finding out what was available with Scala. There seem to be two main contenders at the moment - from scalaz 7 and shapeless. I thought I'd compare the two, to see how they handle the simple name and address record structure used by Simon which is (in scala):

   case class Person (name: String, address: Address, salary: Int)
   case class Address (road: String, city: String, postcode: String)

   // sample Person
   val person = Person("Fred Bloggs", Address("Bayswater Road", "London", "W2 2UE"), 10000)

Lenses from Scalaz 7

A lens itself is a pretty simple affair, consisting only of a pair of functions, one for getting and another for setting the value that the lens describes, and doing this within the context of the container (i.e. the record). In scalaz, these are constructed with a good deal of boilerplate - there are two constructors available to you (lensg and lensu), one which curries the 'setting' function, and the other which does not:

    
   val addressLens = Lens.lensg[Person, Address] (
     a => value => a.copy(address = value),
     _.address
   )   
       
   // or
   
   val nameLens = Lens.lensu[Person, String] (
     (a, value) => a.copy(name = value),
      _.name
   )   

Notice that each lens is defined in terms of two types - that of the value itself and that of its immediate container. Typically, you would then have to get hold of a lens for every atomic value you might wish to access:

   
  val salaryLens = Lens.lensu[Person, Int] (
     (a, value) => a.copy(salary = value),
     _.salary
   )

   val roadLens = Lens.lensu[Address, String] (
     (a, value) => a.copy(road = value),
     _.road
   )

   val cityLens = Lens.lensu[Address, String] (
     (a, value) => a.copy(city = value),
     _.city
   )

   val postcodeLens = Lens.lensu[Address, String] (
     (a, value) => a.copy(postcode = value),
     _.postcode
   )

This soon becomes tedious. However, the true usefulness of lenses comes to light when you compose them:

   
  val personCityLens = addressLens andThen cityLens
  val personPostcodeLens = postcodeLens compose addressLens

i.e. you can stay at the top of your record structure and reach down to the very bowels just by using one of these composite lenses. Scalaz, of course, offers you a shorthand hieroglyphic for these composition functions. So you could write them:

   
  val personCityLens = addressLens >=> cityLens
  val personRoadLens = roadLens <=< addressLens

Now you have your lenses defined, you can use them like this:

  
  def get = salaryLens.get(person)
  // res0: Int = 10000

  def update = salaryLens.set(person, 20000)    
  // res1: Person = Person(Fred Bloggs,Address(Bayswater Road,London,W2 2UE),20000)

  def transform = salaryLens.mod(_ + 500, person) 
  // res2: Person = Person(Fred Bloggs,Address(Bayswater Road,London,W2 2UE),10500)

  def transitiveGet = personCityLens.get(person)
  //res3: String = London

  def transitiveSet:Person = {
    val person1 = personCityLens.set(person, "Wakefield") 
    val person2 = personRoadLens.set(person1, "Eastmoor Road") 
    personPostcodeLens.set(person2, "WF1 3ST")
  }
  // res4: Person = Person(Fred Bloggs,Address(Eastmoor Road,Wakefield,WF1 3ST),10000)
 

With scalaz, you also get good integration with the other type classes you might need to use. So, for example, lenses can be lifted to behave monadically because the %= method applies the update and returns a State Monad.:

  
  def updateViaMonadicState = {
        val s = for {c <- personRoadLens %= {"124, " + _}} yield c
        s(person)
      }
  //res13: (Person, String) = (Person(Fred Bloggs,Address(124, Bayswater Road,London,W2 2UE),10000),124, Bayswater Road)

Lenses from Shapeless

By contrast, Shapeless gets rid of all this boilerplate and allows for composition during the construction of the lenses themselves. It uses a positional notation to define the target field of each lens:

  
  val nameLens     = Lens[Person] >> 0
  val addressLens  = Lens[Person] >> 1
  val salaryLens   = Lens[Person] >> 2
  val roadLens     = Lens[Person] >> 1 >> 0
  val cityLens     = Lens[Person] >> 1 >> 1
  val postcodeLens = Lens[Person] >> 1 >> 2

These can then be used in pretty much the same way as Scalaz 7's lenses. The main difference is that mod becomes modify and function application is curried:

  
  def get = salaryLens.get(person)
  // res0: Int = 10000

  def update = salaryLens.set(person)(20000)    
  // res1: Person = Person(Fred Bloggs,Address(Bayswater Road,London,W2 2UE),20000)

  def transform = salaryLens.modify(person)( _ + 500) 
  // res2: Person = Person(Fred Bloggs,Address(Bayswater Road,London,W2 2UE),10500)

  def transitiveGet = cityLens.get(person)
  // res3: String = London

  def transitiveSet:Person = {
    val person1 = cityLens.set(person)("Wakefield") 
    val person2 = roadLens.set(person1)("Eastmoor Road") 
    postcodeLens.set(person2)("WF1 3ST")
  }
  // res4: Person = Person(Fred Bloggs,Address(Eastmoor Road,Wakefield,WF1 3ST),10000)

As far as I can make out, Shapeless doesn't offer any monadic behaviour.

Which One to Use?

It seems to me that if you're tempted to use lenses, removal of boilerplate is critical. As yet, this doesn't seem possible with Scalaz 7, but I'm sure it's only a matter of time. There are other initiatives as well, for example, macrocosm, an exploration of scala macros, has dynamic lens creation, as does Rillit. But for me, at the moment, Shapeless seems astonishingly elegant.