A few FSharpx examples

FSharpx doesn't currently have any proper documentation, and even comments are lacking despite what ohloh says. We will definitely improve the comments, but a reference documentation isn't going to help at all if you don't know the underlying concepts and how things fit together. A good way to introduce these concepts is by using examples that deal with familiar problems. Stackoverflow has proven to be a great source of real-world use cases for many FSharpx features, which also serve to grow it with new features. Here are the F# questions I answered last week using FSharpx I'd like to elaborate. I recommend following the links to the original questions and reading the other answers for comparison.

List multiplication

The question is about doing a cartesian product. Of course, in F# this is pretty trivial to achieve thanks to list comprehensions, but FSharpx has a couple of functions to help express this more directly:

First there's List.lift2. Its signature is ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list .

If you're familiar with F# you'll notice this is similar to the standard function List.map2, which has the exact same signature. So what's the difference?

List.map2 works pairwise. Its result has the exact same number of elements as the parameters. Let's see an example:

> List.map2 (+) [0;1] [0;2];;

[0;3]

That is, it adds 1st element in the first list to 1st element in the second list, and 2nd to 2nd.

List.lift2 does precisely a cartesian product. Let's try it with the same parameters as above:

> List.lift2 (+) [0;1] [0;2];;

[0;2;1;3]

It adds 1st to 1st, 1st to 2nd, 2nd to 1st, 2nd to 2nd.

Same signature, very different semantics.

The name lift2 comes from lifting a function (a binary function, in this case, hence '2') to a monad (the F# list as a monad in this case). In Haskell this function is generalized to all monads and called liftM2. In F# it's also the same as liftA2, which lifts a function to an applicative functor, because there isn't really a first-class concept of monads or applicatives in F#. As an exercise, try writing the monadic 'bind' and 'return' for an F# list, then lift2 in terms of them. You can also implement lift2 using applicative functors, try it. Both exercises are quite enlightening once they 'click'.

But the question asked for a result in tuples. So we could say:

List.lift2 (fun a b -> a,b) [1..30] [1..30]

Tupling elements is a pretty common operation, so FSharpx offers a function tuple2 that does just that (and tuple3 up to tuple6. If you need more than that you probably shouldn't be using a tuple). To summarize:

List.lift2 tuple2 [1..30] [1..30]

With list comprehensions:

[ for x in [1..30] do
    for y in [1..30] do
        yield x,y ]

I think pointfree style wins here if you're familiar with monads.

Updating nested immutable data structures

In which the developer has a few nested immutable records and wants to write a mapping function that reaches deep inside this nesting. The record types model a role-playing game:

type Monster = { 
    Awake: bool 
}

type Room = { 
    Locked: bool 
    Monsters: Monster list 
}

type Level = { 
    Illumination: int 
    Rooms: Room list 
}

type Dungeon = { 
    Levels: Level list 
}

How to write a mapping function that transforms all Monsters in all Rooms within a particular Level of a Dungeon?

In other words, a function mapMonstersOnLevel : int -> (Monster -> Monster) -> Dungeon -> Dungeon .

Let's roll up our sleeves!

let mapMonstersOnLevel nLevel f dungeon =
  let levelMap (level: Level) =
    { level with Rooms = 
                 List.map (fun room -> 
                            { room with Monsters = List.map f room.Monsters }) level.Rooms }
  { dungeon with Levels = 
                 List.mapi (fun i level -> 
                             if i = nLevel then levelMap level else level) dungeon.Levels }

Using lenses we can express this much more concisely and elegantly. After the dreaded but necessary boilerplate for lenses (each field in each record must have an associated lens explicitly spelled out), we are left with:

let mapMonstersOnLevel nLevel f =
    Dungeon.levels >>| Lens.forList nLevel >>| Level.rooms >>| Lens.listMap Room.monsters
    |> Lens.update (f |> List.map |> List.map)

Lenses are quite intuitive, I think it's pretty easy to grasp what's hapenning there, even if you've never seen lenses before. The only difference is that because a lens Update is a Get, followed by the transforming function, followed by a Set, this isn't as effective as the first version. It can be optimized, but I'm not sure it's worth it, updating an element in an immutable list is still O(n), it doesn't matter much if it needs an extra pass.

Exception handling in pipeline sequence

An initial state is pipelined along a series of functions that modify this state. The state in question is a point on a plane, but that's not important. Problem is, each function can throw, and when that happens the whole computation must be aborted and an error must be shown.

Initially, the problem is posed like this:

let startingPosition = 0. ,0.

let moveByLengthAndAngle l a (x,y) = x,y // too lazy to do the math
let moveByXandY dx dy (x,y) = x+dx, y+dy
let moveByXandAngle dx a (x,y) = x+dx, y

let finalPosition =
    startingPosition
    |> moveByLengthAndAngle x1 a1 
    |> moveByXandY x2 y2
    |> moveByXandAngle x3 a3
    |> moveByLengthAndAngle x4 a4
    // etc...

Instead of doing this, let's represent the computation as a list of partially applied functions with the associated error messages:

let actions = 
    [
        moveByLengthAndAngle x1 a1, "failed first moveByLengthAndAngle"
        moveByXandY x2 y2, "failed moveByXandY"
        moveByXandY x3 y3, "failed moveByXandY"
        moveByXandAngle x3 a3, "failed moveByXandAngle"
        moveByLengthAndAngle x4 a4, "failed second moveByLengthAndAngle"
    ]

And then fold over this list of actions, starting with the initial point and accumulating the result of each function. In the folding function we must also catch any potential exception and put the error message instead, and abort the rest of the computation. But the state is a pair of floats and the error message obviously a string, so we model the actual state as a Choice of either the pair of floats or a string (i.e. Choice<float * float, string> ):

let finalPosition = 
    let evalToChoice (f,message) a =
        try
            f a |> Choice1Of2
        with _ -> Choice2Of2 message
    let folder a f = 
        match a with 
        | Choice2Of2 a -> Choice2Of2 a 
        | Choice1Of2 a -> f a
    actions 
    |> List.map evalToChoice
    |> List.fold folder (Choice1Of2 startingPosition)

All that's left to do is pattern match on finalPosition to see if the computation ended up as error or completed successfully:

match finalPosition with
| Choice1Of2 (x,y) -> 
    printfn "final position: %f,%f" x y
| Choice2Of2 error -> 
    printfn "error: %s" error

FSharpx has a couple of abstractions (mostly borrowed from Haskell, as usual) that help reduce the clutter here:

Firstly, FSharpx defines a monad around Choice1Of2 / Choice2Of2. This is like the Either monad defined in Haskell or Scalaz, except we call it Choice because... well, the F# type is already called Choice. So we have Choice.bind and returnM (actually 'return' is just the constructor Choice1Of2). The convention here is that Choice1Of2 carries the successful branch of the computation and Choice2Of2 carries the error.

FSharpx also defines bifunctor for Choice. In Scalaz and Haskell this is a typeclass (of which Either is an instance), but in FSharpx this is simply two functions bimap and mapSecond. Bimap takes two mapping functions, and uses the first one to map the Choice1Of2 part of a Choice, and the other one to map the Choice2Of2 part. mapSecond only maps the Choice2Of2 part of a choice. What about mapFirst? It's simply map.

Since Choice/Either is frequently used in pure functional programming to represent errors, and we're working in an impure language, it makes sense to have a library function to convert a function that throws as a means to report an error into a function that returns a Choice, where the Choice2Of2 part is the potential exception. This seems to be pretty common in Scala, and it's what Choice.protect in FSharpx does. The signature is pretty explicit: ('a -> 'b) -> 'a -> Choice<'b,exn>

Putting all the pieces together:

let finalPosition = 
    let folder position (f,message) =
        Choice.bind (Choice.protect f >> Choice.mapSecond (konst message)) position
    List.fold folder (Choice1Of2 startingPosition) actions

Haskellers have long ago recognized this folding with a monadic result and abstracted it into a generic function foldM. As usual, in F# we can't express this generically for any monad, but we can write it for every monad. With foldM the code looks like this:

let finalPosition = 
    let folder position (f,message) = 
        Choice.protect f position |> Choice.mapSecond (konst message)
    Choice.foldM folder startingPosition actions

A different approach to the problem is to rethrow the message as an exception, instead of using Choices. This is quite concise as well:

let finalPosition() = 
    let evalRethrow (f,message) a =
        try f a with _ -> failwith message
    actions
    |> List.map evalRethrow
    |> List.fold (|>) startingPosition

Instead of pattern matching over the result, you'd invoke this function in a try..with block:

try
    let x,y = finalPosition()
    printfn "final position: %f,%f" x y
with e -> 
    printfn "error: %s" e.Message

The problem with using exceptions is that they're not really part of the type system. The function finalPosition is of type unit -> float*float . This doesn't say it might throw an exception, so you can't statically enforce handling the error case. Also, exceptions are actually misused here: having an error in the computation is an expected result, not a programming error. I recommend reading Errors vs Exceptions for more information on this. The terms 'exception' and 'error' may sometimes be used in one way or the other, but it's always useful to make the distinction.

Also worth noting is how representing the computations as a list of actions with associated data (in this case, the messages) allows us to freely choose how to evaluate it.

Using F# datatypes in C#

FSharpx is not just for F# consumers. I blogged before about using the F# runtime as a library in C# apps. FSharpx adds some sugar so you can use F# persistent collections in C# quite comfortably. Here's an example:

var a = FSharpList.Create(1, 2, 3);
var b = a.Cons(0);
b.TryFind(x => x > 4)
 .Match(v => Console.WriteLine("I found a value {0}", v),
        () => Console.WriteLine("I didn't find anything"));

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.