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"));