This talk by Jesús Lopez Gonzales has been quite clear (at least to my challenged functional understanding). As strange as it may sound the whole idea of optics (in Functional Programming) is to solve a problem that exists only because of the functional paradigm. Aside from cheap humor, it makes sense – in structured programming, you do the same by forbidding the use of the goto statement, and you need other tools (e.g. break, continue, structured statements) to do the same job in a safe, sound and controlled way.

You can find sources for the running example here: https://github.com/hablapps/dontfeartheoptics.git

But I don’t want to steal the stage. As usual, all mistakes and false predicates are mine (my only defense is that the talk was performed without a mike and loudspeaker system).

Just one last note, before starting – the original slides of the presentation used a compact syntax, relying on Scala’s high sucrose diet. I opted for a more verbose syntax that makes clear to those less fluent in Scala what’s happening behind the sugar curtain.

Functional Programming is a programming paradigm […] that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

(from Wikipedia)

In functional programming, we decide not to change the state of variables once assigned. That means that when we want to change something we have to create a new instance from the existing one.

Consider the position class:

case class Pos(i: Int, j: Int )
pos1 = Pos(1,1)

In order to change to position to a new one, the “changing” method just takes the existing pos1 and creates a new instance with the new state:

pos2 = pos1.move(1,2)

The running example for this talk is a CandyCrush clone. Here are the main classes:

case class Game( ups: Int, level: option[Level], )
case class Level( targetScore: Long,
                  targetMoves: Long,
                  board: Board,
                  currentScore: Long,
                  currentMoves: Long )
case class Board( height: Int, width: Int, matrix: Map[Pos,Option[Candy]])

Modules are defined as follows:

• Candy REPL – IO
• Candy Business logic – state program
• Candy data layer – data structures & optics

To face problems posed by state immutable we resort to the Half-Life narration – who better than Gordon Freeman – the man with a big lambda on his breast – could help us in the process?

The talk uses an explorative approach – you may want to explore the area to locate the problem (the Alien), then try to solve it using some techniques (equipping new weapons), and then refine the solution until you find an elegant way to fix the problem.

The first enemy to defeat is how to keep the state unchanged.

CandyState.scala is the source file where “getter and setters” are located). There are several points where you need to update the state as the game progresses.

def modifyScore( f: Long => Long) : Level => Level..
def modifyMatrix( f: CandyMatrix => CandyMatrix ) : Level => Level

[NdM: note that specific to this paradigm these methods accept a function that transforms score (or playfield) into a new score (or playfield) and returns a function that changes the Level accordingly. I found this revealing and somewhat mind-boggling.]

How would you do it in a traditional way?
In order to modify you need to copy:

def modifyScore( f: Long => Long ) : Level => Level =
  lv => lv.copy(currentScore = f(lv.currentScore))

def modifyMatrix( f: CandyMatrix => CandyMatrix ) : Level => Level
lv => lv.copy( board = lv.board.copy( matrix = f(lv.board.matrix)))

This is not straightforward, at least not in general, because you need to copy through several indirection levels. Functional programming is about elegance and modularity, not this.

(Alien identified!)

Lens comes to the rescue (or, as Jesus put it, Lens – the crowbar in the half-life analogy – is the weapon to equip). The lens is a parametric class defined over two types: S – the whole and A – the part:

abstract class Lens[S,A] {
    def get( s: S): A
    def set(a: A): S => S
}

get method accepts a whole and returns a part. set accepts a part and tells you how to change the whole to incorporate that part.

val _currentScore: Lens[Level,Long] =
    Lens[Level,Long]( 
        lv => lv.currentScore
    )(
        cs => lv => lv.copy(currentScore=cs)
    )
val _board : Lens[Level,Board] =
    Lens[Level,Board](
        lv => lv.board
    )(
        br=>lv=>lv.copy(board=br)
    )
val _matrix : Lens[Board,CandyMatrix] =
    Lens[Board,CandyMatrix](
        bd => bd.matrix
    )(
        mx => bd => bd.copy(matrix=mx)
    )

modifyScore2( f: Long => Long) : Level => Level = {
    level : Level =>
        Level.currentScore.set( f( level.currentScore ))(level)
}

The code works, but it is lengthy and boring to write. So we can take advantage of the Lens defined for us by the @Lenses annotation.

[NdM: I’m going to expand the talk a little bit here because I lost some passages and I reconstructed them thanks to my Scala-speaking friends]

This annotation instructs the compiler to create one lens method in the companion object for each case class field. [NdM: Oddly enough, for us coming from traditional programming languages, the lens has the same name as the case class field].

[NdM: original example exploited import to inject in the current scope the companion object’s fields, creating a bit of confusion in my mind. In the following examples I will avoid this shortcut in favor of readability].

What if we want to extract the matrix from a level? Operationally we have to navigate through the board (level->board->matrix). This can be done via composition, using the verb composeLens :

def getMatrix2 : Level => CandyMatrix = (Level.board composeLens Board.matrix).get

[NdM: my Scala-speaking friend also told me that def has been used without a real advantage over val. Having used val would have avoided an unneeded function call.]

The same can be applied to modify:

def modifyMatrix2( f: CandyMatrix => CandyMatrix ) : Level => Level = 
    (Level.board composeLens Board.matrix).modify(f)

This syntax is slick, but still more verbose than say Haskell where you write just a dot instead of the composeLens verb.

2nd Enemy – Threading State Zombie (State Monads)

Consider the function

crushPos( pos: Pos): Level => (Level, Long)

Its purpose is to crash a given position. This is accomplished by updating the map and updating the score. Additionally, we want the function to return a pair composed of the level and the new score. The first implementation you may want to try is to navigate through the level to change the matrix, then navigate through the updated version of the level to update the score, and then prepare the pair with the updated level and the score.

def crushPos( pos: Pos) : Level => (Level, Long) = {
    lv0 =>
        val lv1 = (board composeLens matrix).modify(mx => mx.updated(pos, None))(lv0)
        val lv2 = currentScore.modify( cs => cs +1)(lv1)
        (lv2, currentScore.get(lv2))
}

This works, but it is error-prone because the programmer must ensure to properly pipe all the changes through the transformations.

The new weapon is the State:

abstract class State[S,A](run : S => (S,A))

This class defines a mechanism to execute a given action on an object and produce the updated object and a value. And it can be used like:

def crushPos2(pos: Pos): Level => (Level , Long) = {
    lv0 =>
        val (lv1, _ ) = State[Level,Unit] (
            lv => {
                (board composeLens matrix).modify(mx => mx.updated(pos, None))
                ((lv), ())
            }
        ).run( lv0 )
        State[Level,Long] (
            lv => {
                val nlv = currentScore.modify(cs => cs + 1)(lv)
                (nlv, currentScore.get(nlv))
            }
        ).run(lv1)
}

This may be more elegant but can be hardly defined as better, and nonetheless still requires the programmer to properly set up the execution pipe. [NdM: also note that the first part (from val to run( lv0 )  may be replaced by a more compact val lv1 = (board composeLens matrix).modify(mx => mx.updated(pos, None))( lv0 )  ]

This can be improved by using an implicit MonadState, which is a class implicitly built from a State class that can be bound together using the >> operator. In code:

case class State[S,A](run : S => (S,A))

implict def monadState[S]: monad[State[S,?]] = ...

Our code becomes:

def crushPos3(pos: Pos): State[Level, Long] = {
    State[Level, Unit] {
        lv =>
            val lv1 = (board composeLens matrix).modify(mx => mx.updated(pos, None))(lv)
            (lv),()
    } >>
    State[Level,Long] {
        lv =>
            val nlv = currentScore.modify( cs => cs +1)(lv)
            (nlv,currentScore.get(nlv))
    }
}

[NdM: be careful in placing the >> operator! First IntelliJ is not able to recognize it and marks it as an unknown operator; second thanks to Scala’s forgiveness of syntax punctuation, you need to place >> on the same line of the closing bracket. I couldn’t figure out the right way to write this until I mailed the author of the talk for help. He responded quickly and kindly and set me in the right direction. Thanks, Jesus]

[NdM: a quick word on binding. Bind is the same as flatMap, that is the way monads transform their content. In this case, the binding allows you to compose the two-run action into one. Since the computation accepts one value and produces two, you may wonder what happens to the side value (in our case the score) of the first run. Answer – it gets discarded and only the last one is produced in the final result]

MonadState can be composed so they pipe the result one through the other.

def crushPos4( pos: Pos ) : State[Level, Long] =
    (board composeLens matrix).mod(mx => mx.updated( pos, None)) >> currentScore.mod(_ + 5)

[NdM: now, this is a bit more complex to digest – where does the .mod come out? And more importantly, how does .mod know what to return? .mod is a method of the StateLens object (well, nearly true, but true enough for the sake of this analysis). Always remember that you are not dealing with actual values, but you are forging functions that will need to be called/applied to actual values. Note that the lenses in the expression are both on the Level class, so the state generated by mod operates on the Level class. The additional type is derived by the right operand of the >> operator.]

Enemy 3: optional antlion

So far so good, but there are still other entities that cannot fit properly in the picture. What about getting and modifying the current score from the Game? The problem we face is that level is an option in Game. Lenses can’t be used with a plain-vanilla approach.

Let’s try a first attempt at the solution:

def getScore: State[Game, Option[Long]] =
    level.extract.map( olv => olv.map( lv => currentScore.get(lv)))

def modifyScore(f : Long => Long) : State[Game,Unit] =
    level.mod_(olv. => olv.map(lv => currentScore.modify(f)(lv)))

extract  is a method of the State

Nice, but cumbersome. The abstraction we can use now is the Prism (which is defined in monocle, roughly in the following way):

abstract class Prism[S,A] {
    def getOption : S => Option[A]
    def reverseGet : A => S
}

The first method takes an object and produces an option, the second method rebuilds the object given a part. So, let’s define our prism:

import monocle.Prism

def mySome[A] : Prism[Option[A], A] = Prism[Option[A],A]( s => s)(a=>Some(a))

This prism deals  with an Option[A], but monocle already provides you with this tool and it’s called some :

import monocle.std.option.some

def getScore2: State[Game, Option[Long]] =
    (level composePrism some composeLens currentScore).extract

def modifyScore2( f : Long => Long) : State[Game,Unit] = 
    (level composePrism some composeLens currentScore).mod_(f)

Final Enemy: Multiple Fast Zombies

Now we want to crush an entire column of the board.

We can combine lenses and prisms into something else:

abstract class Optional[S,A] {
    def getOption(s: S): Option[A]
    def set(a: A): S => S
}

As for the Prims we have a getOption method that exposes the Option, but, instead of the reverseGet, there is a set that transforms S into another S provided an A.

Optionals  can be created by composing prisms and lenses as follows:

val op: Optional[Game,CandyMtrix] =
    level composePrism some composeLens board composeLens matrix

So that we can write our first iteration of the crushColumn method as –

def crushColumn(j: Int): State[Game, Unit] =
    op.mod_(
        mx => mx.map {
            case (p,_) if p.j == j => (p,None)
            case x => x
        }
    )

This function operates on the game matrix and removes the candy when the column of the position is the same as j.

It is not bad per se, but we are doing this in a manual way. The solution could be improved by using a filterIndex:

def crushColumn2( j : Int ) : State[Game,Unit] =
    op.mod_(
        mx => filterIndex[CandiMatrix,Pos,Option[Candy]]( p => p.j == j ).set(None)(mx)
    )

Let’s see how to automatize it. Let’s introduce the abstract metaclass Traversal:

abstract class Traversal[S,A] {
    def modifyF[F[_]: Applicative](f:A => F[A])(s:S): F[S]
}

Now it is possible to compose the Traversal with other lenses such as:

def crushColumn3( j: Int ) : State[Game,Unit] =
    (op composeTraversal filterIndex((p: Pos)=> p.j == j )).assign_(None)

FilterIndex is a monocle function, that along with the implicit mapFilterIndex allows the lens to apply over the map collection.

Since compose syntax may tend to be a bit verbose, you can also use the following operators:

• ^<-?  compose with prism
• ^|->  compose with a Lens
• ^|->> compose traversal

Conclusions: Optics are abstractions for changing parts of wholes. These abstractions are composable to access complex data. Monacle library provides hybrid of concrete e Van Laarhoveen optics [NdM: sorry I missed the explanation entirely]. State monads encapsulate state threading and produce output values.

Max’s comment – The talk has been very helpful in improving my understanding of this aspect of functional programming. I still find Scala syntax to be a bit on the verge of cryptic and dealing with new concepts doesn’t help either. Composing stuff in the way functional programming does is a really powerful mechanism that enables the programmer to recycle code in an effective manner.

I find that the use of symbols to further reduce the characters count is really dangerous. But this is a topic for another post. Let’s just say that Scala is endangered of write-only code 🙂 Looking forward to attending the next Lambda World!