Tuesday, November 15, 2011

Lenses in F#

Consider the following record types in F# :

type Car = { 
    Make: string 
    Model: string 
    Mileage: int 
}

type Editor = { 
    Name: string 
    Salary: int 
    Car: Car 
}

type Book = { 
    Name: string 
    Author: string 
    Editor: Editor 
}

Given a Book we can trivially retrieve its editor's car mileage:

let mileage = aBook.Editor.Car.Mileage

Setting the mileage is a bit more problematic though. If this were mutable, we could just do:

aBook.Editor.Car.Mileage <- 1000

But it's not, so we use F# copy-and-update syntax:

let book2 = { aBook with Editor = 
                { aBook.Editor with Car = 
                    { aBook.Editor.Car with Mileage = 1000 } } }

That's a lot of fun! Not. Can we make this prettier?

Or if we want to modify a property, for example add 1000 to the mileage, even with mutable properties we have to do:

aBook.Editor.Car.Mileage <- aBook.Editor.Car.Mileage + 1000

If this were C# we could just say:

aBook.Editor.Car.Mileage += 1000;

That's pretty convenient, so how can we implement something similar in F# with immutable records?

In summary, can we gain back some of the convenience of mutable properties?

The key is to make properties first-class values.

First we ask ourselves: what's a property getter? It's a function 'a -> 'b , where 'a is the record type and 'b is the property type.

A setter for a mutable property is a function 'b -> 'a -> unit . But we're interested in setters for immutable records. Such a setter is a function 'b -> 'a -> 'a , i.e. it takes the new value, the record, and returns the modified record.

So we have a pair of functions:

Get : 'a -> 'b

Set : 'b -> 'a -> 'a

Let's put them together in a record, which we'll call "Lens":

type Lens<'a,'b> = {
    Get: 'a -> 'b
    Set: 'b -> 'a -> 'a
}

Modeling a 'modify' operation on top of this is easy: you get the original value, modify it with some function, then set the modified value back:

with member l.Update f a = 
    let value = l.Get a 
    let newValue = f value 
    l.Set newValue a

Note that this Update is still purely functional.

Let's create some lenses for the record types we declared above:

type Car with
    static member mileage = 
        { Get = fun (c: Car) -> c.Mileage
          Set = fun v (x: Car) -> { x with Mileage = v } }

type Editor with
    static member car = 
        { Get = fun (x: Editor) -> x.Car 
          Set = fun v (x: Editor) -> { x with Car = v } }

type Book with
    static member editor = 
        { Get = fun (x: Book) -> x.Editor 
          Set = fun v (x: Book) -> { x with Editor = v } }

What we need now is a way to compose these lenses, so we can go from a book to a mileage and update it:

let inline (>>|) (l1: Lens<_,_>) (l2: Lens<_,_>) = 
    { Get = l1.Get >> l2.Get 
      Set = l2.Set >> l1.Update }

Lenses are closed under composition. That is, the sequential composition of any two lenses is a lens.

We can now create a lens that goes from a book instance to the mileage, by composing primitive lenses:

let bookEditorCarMileage = Book.editor >>| Editor.car >>| Car.mileage

let mileage = bookEditorCarMileage.Get aBook

let book2 = aBook |> bookEditorCarMileage.Set 1000

We can also implement (+=) generically for any lens focused on a type supporting (+) (e.g. int, float, decimal):

let inline (+=) (l: Lens<_,_>) v = l.Update ((+) v)

let book2 = aBook |> bookEditorCarMileage += 1000

Thanks to lenses we now have much of the convenience of the mutable properties, while at the same time making properties first-class composable objects and retaining purity.

Lenses and the State monad

It's also possible to lift lens operations to the State monad: this gives an even more imperative feel, while still retaining referential transparency. Here's an example (using FSharpx's State monad):

let promote =
    state {
        let! oldSalary = Lens.getState Editor.salary
        do! Editor.salary += 1000
        return oldSalary
    }
let oldSalary, promotedTom = promote tom
printfn "Tom used to make %d, after promotion he now makes %d" oldSalary promotedTom.Salary

Conclusions

I've barely scratched the surface of lenses here. The general concept of lenses is that a lens allows to focus on a particular element in a data structure, both to view it and to update it. More formally, lenses can be described as well-behaved bidirectional transformations. Lenses must follow some laws (which I haven't shown here) in order to be well-behaved.

Lenses are being actively researched, and because of their genericity they have been applied in widely different areas, for example functional reactive AJAX applications (lenses for Flapjax) and configuration management.

There's even a whole research programming language around lenses called Boomerang.

Virtual Combat Cards, a tool to assist Dungeons & Dragons Dungeon masters, written in Scala, makes use of lenses as first-class properties (code is here if you want to check it out).

Scalaz implements the basic plumbing and definition of lenses for Scala, and this F# implementation draws heavily from that code. Hat tip to the Scalaz devs. Haskell has a similar package Data.Lenses.

When using lenses for properties as I've shown here, there's the problem of having to define the primitive lenses that wrap the actual .NET properties. Haskell solves that using Template Haskell, and Scala has a compiler plugin currently under development which automatically generates this boilerplate. It may be possible to write a type provider to do this in F# 3.0, but I haven't looked into this yet.

F# code shown here coming soon to FSharpx.

10 comments:

Nick Palladinos said...

One small error
This is the correct composition
let inline (>>|) (l1: Lens<_,_>) (l2: Lens<_,_>) =
{ Get = l1.Get >> l2.Get
Set = l2.Set >> l1.Update }

Mauricio Scheffer said...

@Nick : thanks, in the actual code I call this 'compose' then bind (>>|) to the flipped 'composed', but forgot to flip it here trying to make it simpler.

Denys Goff said...

But it is not through the lens definition forced to always implement getter AND setter, or in other words how you implement a readonly C# Property with Lenses?

Mauricio Scheffer said...

@Dennis : you could write a "forgetful" lens modeling a readonly C# property, but it would violate the SetGet law (also called PutGet or Acceptability law). A lens that doesn't comply with this law is not well-behaved. See these slides for a summary of lens laws. I haven't checked how, exactly, violating this law harms composability. I bet you can come up with such an example ;-)
Ultimately though, a readonly property isn't a bidirectional transformation so I don't think it would gain much from being modeled as a lens instead of just trivially modeling it as a function.

Denys Goff said...

Supposedly you can solve it with Lenses - http://comonad.com/reader/2012/mirrored-lenses, but i did not understand this Haskell stuff.

Mauricio Scheffer said...

Yes, I have seen that article. It uses typeclasses and higher-kinded types, which we don't have in .NET, so I don't think it's viable to express that in F#.
It still looks overkill, i.e. as I said a getter is just a function.
Polymorphic lenses are interesting though, I'll try to investigate them when I get some time.

Tiago said...
This comment has been removed by a blog administrator.
Tiago said...
This comment has been removed by the author.
Edward Kmett said...

The implementation that folks use in Haskell is actually http://hackage.haskell.org/package/lens -- The `lenses` package was never really used by anyone.

Mauricio Scheffer said...

@Edward : indeed! Back when I wrote this in 2011, your lens library wasn't around yet ;-)