Monday 4 June 2012

Scala: Lenses 1

If U ever had a task on updating nested immutable structures - U might found it as non-clean code task, especially it's hard to guard solution from colleges :p

There is nice fitting solution coming from function programming theory, that shines in Scala as well.

Intro 

"Lenses are bidirectional transformations between pairs of connected structures. Asymmetric lenses —where one of those two connected structures is taken to be primary —have been extensively studied. Lenses were first proposed to solve the view- update problem of tree-like data structures by Foster et. al and have also been applied to the construction of a relational database query language."

Tony Morris 

Problem

Imagine gammy model from two classes:

    case class Weapon(name: String, ammo: Long)
    case class Soldier(rank: Int, weapon: Weapon)

case keyword is used because of Scala generates useful copy helper method, which returns a new instance of changed object. 

    val soldier2 = soldier.copy(rank = 3)

Soldier has a weapon, changing direct fields are easy thanks to generated copy. Requirement to change weapon - brings boilerplate to solution.
Lets do a coding, target change a rank:

    def modifyRank(f: Int => Int)(s: Soldier): Soldier = {
        s.copy(rank = f(s.rank))
    }

and how to change a weapon of soldier:

    def modifyWeapon(f: Weapon => Weapon)(s: Soldier) = {
        soldier.copy(weapon = f(soldier.weapon))
    }

There are potentially as many modify(set) functions as there are record fields including sub elements, each requiring us to build it. However, the problem is even more visible. Lets create the getter method for weapon name.

    def getSoldierWeaponName(s: Soldier) = s.weapon.name

Additionally, u might want to create a modify method for soldier's weapon ammo.

    def setWeaponAmmo(s: Soldier)(ammo: Long) = {
        val weapon: Weapon = soldier.weapon
        soldier.copy(weapon = weapon.copy(ammo = ammo))
    }

Still looks not bad, everything is immutable, functions are abstractions around changing the structure. But at the end this solution is going to be problematic because the count of functions to implement is proportional is growing fast, and boilerplate code in functions are coming to be bigger than our model.
Common picture is:
 
    get: Rec => Field
    set: (Rec, Field)=> Rec

And as we got from here an example, to change soldiers rank is:

    Soldier => Int
    Int => Soldier

Lenses

It's time to introduce bidirectional lens, the model that is solves bidirectional relationship structures ( defined over record type R and field type F. There are two functions inside for get and update operations:

    case class Lens[R, F](get: R => F, set: (R, F) => R)

and implementing this for rank from soldier:

    val rankL = Lens[Soldier, Int](
        get = _.rank,
        set = (s, r) => s.copy(rank = r)
    )

At the end we can create modify function based on lenses:

    def modify[R, F](l: Lens[R, F])(f: F => F): R => R =
            r => l set(r, f(l get r))
 

As U can see still isn't very differ to direct modify methods, but it's incapsulate complexity of object's structure and produces reusable model. Little bit improved to DRY practices. Lenses level of abstraction is very similar to Model-View-Presenter pattern. Unfortunately working with immutable data sometimes looks very complicated to getter and setters, even worse, it requires from us to bring a boilerplate. There is a nice implementation from scalaz library. I remember 10 years ago there was an era of code-generation tools, it was very popular weapon against boilerplatem then welcome for Lensed Compiler Plugin. THis plugin generate lenses for case classes automatically.

Lens Laws

Here it's time to remember that function programming is coming with the mathematical mess, remember Monads and their laws?

1. Get-set returns original value
     
    ∀ r f. lens.get(lens.set(r, f)) == f

2. Changing field value to itself returns the same record

    ∀ r. lens.set(r, lens get r) == r

3. Applying to field f2 then f1 is the same as setting it once value f1. f2 is lost in time.

    ∀  r  f1 f2. lens.set(lens.set(r, f2), f1) == lens.set(r, f1)

Prefer talking in scala?

1. Law 1

    def lensLaw1[R, F](r: R, f: F)(lens: Lens[R, F]) =
        lens.get(lens.set(r, f)) == f

    assert(lensLaw1(soldier, 5)(rankL))

2. Second

    def lensLaw2[R, F](r: R)(lens: Lens[R, F]) = lens.set(r, lens get r) == r

    assert(lensLaw2(soldier)(rankL))

3. Third

    def lensLaw3[R, F](r: R, f1: F, f2: F)(lens: Lens[R, F]) =
        lens.set(lens.set(r, f2), f1) == lens.set(r, f1)

    assert(lensLaw3(soldier, 3, 5)(rankL))

Next steps:

I recommend you to looks into the scalaz implementation for lenses, you will like it.
Looks like Lenses compose method is required to be discussed as a nice solution.

No comments:

Post a Comment