Objects and functional programming

In a recent question on Stackoverflow, someone asked “when to use interfaces and when to use higher-order functions?”. To summarize, it’s about deciding whether to design for an interface or a function to be passed. It’s expressed in F#, but the same question and arguments can be applied to similar languages like C#, VB.NET or Java.

Functional programming is about programming with mathematical functions, which means no side-effects. Some people say that “functional programming” as a paradigm or concept isn’t useful, and all that really matters is being able to reason about your code. The best way I know to reason about my code is to avoid side-effects or isolate them as much as possible.

In any case, none of this says anything about objects, classes or interfaces. You can represent functions however you like. You can write pure code with objects or without them. OOP is effectively orthogonal to functional programming. In this post I'll use the terms 'objects', 'classes', 'interfaces' somewhat interchangeably, the differences don't matter in this context. Hopefully my point still gets across.

Higher-order functions are of course a very useful tool to raise the level of abstraction. However, many perhaps don’t realize that any function receiving some object as argument is effectively a higher-order function. To quote William Cook in “On Understanding Data Abstraction, Revisited”:

“Object interfaces are essentially higher-order types, in the same sense that passing functions as values is higher-order. Any time an object is passed as a value, or returned as a value, the object-oriented program is passing functions as values and returning functions as values. The fact that the functions are collected into records and called methods is irrelevant. As a result, the typical object-oriented program makes far more use of higher-order values than many functional programs.”

So in principle there is little difference between passing an interface and passing a function. The only difference here is that an interface is named and has named functions, while a function is anonymous. The cost of the interface is the additional boilerplate, which also means having to keep track of one more thing.

Even more, since objects typically have many functions, you could say that you’re not just passing functions as values, but passing modules as values. To put it clearly: objects are first-class modules.

As an aside, the term “first-class value” doesn’t have a precise definition, but I find it useful to wield it with the definition given in MSDN or the Wikipedia.

Objects are also parametrizable modules because constructors can take parameters. If a constructor takes some other object as parameter, then you could say that you’re parameterizing a module by another module.

In contrast to this, F# modules (more generally, static classes in .NET) are not first-class modules. They can’t be passed as arguments, you can’t do something like creating a list of modules. And they can’t be parameterized either.

So why do we even bother with modules if they’re not first-class? Because it’s easier to pick just one function out of a module to use or to compose. Object composition is more coarse-grained. As Joe Armstrong famously said: “You wanted a banana but you got a gorilla holding the banana”.

Back to the Stackoverflow question, what’s the difference between:

module UserService =
   let getAll memoize f =
       memoize(fun _ -> f)

   let tryGetByID id f memoize =
       memoize(fun _ -> f id)

   let add evict f name keyToEvict  =
       let result = f name
       evict keyToEvict
       result

and

type UserService(cacheProvider: ICacheProvider, db: ITable<User>) =
   member x.GetAll() = 
       cacheProvider.memoize(fun _ -> db |> List.ofSeq)

   member x.TryGetByID id = 
       cacheProvider.memoize(fun _ -> db |> Query.tryFirst <@ fun z -> z.ID = ID @>)

   member x.Add name = 
       let result = db.Add name
       cacheProvider.evict <@ x.GetAll() @> []
       result

The first one has some more parameters passed in from the caller, but you can imagine what it would look like. I probably wouldn’t arrange things like either of them, but for one, both lack side-effects. To the first one, you can pass pure functions. To the second one, you can pass implementations of ICacheProvider and ITable with pure functions.

However if you take a good look at the second one, you’ll see that every method uses both cacheProvider and db. So in this case it’s not so bad to pass a couple of gorillas. And it gives the reader a lot more information about what’s being composed, as opposed to a signature like

add : evict:('a -> unit) -> f:('b -> 'c) -> name:'b -> keyToEvict:'a -> 'c

To summarize: The beauty of functional programming lies in being able to reason about your code. One of the easiest ways to achieve this is to write code without side-effects. Classes, interfaces, objects are not opposed to this. In object-capable languages, objects can be a useful tool. Here I talked about objects as modules, but they can model other things too, like records or algebraic data types. They can be easily overused though, especially by programmers new to functional programming. Consider carefully if you want to be juggling gorillas rather than bananas!

A tale of equational reasoning in F#

My implementation of formlets, based on the original paper, composes quite a few applicative functors. They're all standard applicatives. For example, the one that looks up values from the submitted form is just a specialized Reader (i.e. a Reader with one of the type parameters fixed to the form type). The applicative responsible for generating form element names is a State. Another two of the applicatives are actually the same applicative, only specialized with different type parameters.

Since many of these are already implemented in FSharpx, I decided to use those implementations instead... After making the necessary changes and getting it to compile, I ran the tests and got a lot of failures. Many of the outputs involving lists were exactly in inverse order! I traced it down to the composition of applicatives, but I couldn't figure out what was wrong.

I'll illustrate with a simple but concrete example. We'll use the Writer applicative. Essentially, the effect of this applicative is appending values with a monoid. Here we'll just accumulate on a list.

This is much simpler to see in code:

let puree x = [],x 
let ap (x1,x2) (f1,f2) = f1 @ x1, f2 x2 

An example using it:

puree (-) |> ap (["a";"b"],3) |> ap (["c";"d"],2)

This evaluates to (["a"; "b"; "c"; "d"], 1) , i.e. it concatenates the lists (the effect) and applies the function to the second value in the tuple.

So far so good. Now let's try to compose this applicative with itself. Composing applicatives is easy: as I explained in a previous article, just lift ap and apply pure to pure:

let lift2 f a b = puree f |> ap a |> ap b

let composedPure x = x |> puree |> puree 
let composedAp x f = lift2 ap x f

Let's see how this works:

composedPure (-) 
|> composedAp (["a"; "b"], ([1; 2], 2)) 
|> composedAp (["c"; "d"], ([3; 4], 3))

which gives us (["c"; "d"; "a"; "b"], ([1; 2; 3; 4], -1))

Uh oh, the outer applicative has its effect flipped! The result should have been (["a"; "b"; "c"; "d"], ([1; 2; 3; 4], -1)) . What went wrong here?

One difference in this code with the Haskell definition of applicative functors is that I flipped the parameters of ap. This allowed us to apply ap with a pipe as is usual in F#. You could also use a forward and a backward pipe to "infixify" a function but it just doesn't look right to me. Even though it compiles and apparently looks correct, this difference broke our applicative composition.

In order to fix the applicative composition and still keep the convenient flipped parameters, we have to change composedAp to:

let flip f a b = f b a

let composedAp x f = flip (lift2 (flip ap)) x f

The question now is: do you really understand why this composedAp is correct, just by looking at its definition, while the previous one would flip one of the applicatives and not the other?

To be honest, I don't. But simple equational reasoning can tell us what went wrong. Let's start with the original (incorrect) definition of composedAp:

  lift2 ap x f 
= puree ap |> ap x |> ap f              // lift2 definition
= ap f (ap x (puree ap))                // |> definition
= ap (f1,f2) (ap (x1,x2) (pap1, pap2))  // expand tuples, apply puree
= ap (f1,f2) (pap1 @ x1, pap2 x2)       // apply inner ap
= pap1 @ x1 @ f1, pap2 x2 f2            // apply outer ap
= [] @ x1 @ f1, ap x2 f2                // apply puree
= x1 @ f1, ap (x21, x22) (f21, f22)     // simplify empty list, expand tuples
= x1 @ f1, (f21 @ x21, f22 x22)         // apply ap

Now the correct composedAp, for comparison:

flip (lift2 (flip ap)) x f 
= flip (fun f a b -> ap b (ap a (puree (flip ap)))) x f     // lift2 definition
= (fun f a b -> ap b (ap a (puree (flip ap)))) f x          // apply flip
= ap x (ap f (puree (flip ap)))                             // apply lambda
= ap (x1,x2) (ap (f1,f2) (pfap1, pfap2))                    // expand tuples, apply puree
= ap (x1,x2) (pfap1 @ f1, pfap2 f2)                         // apply ap
= pfap1 @ f1 @ x1, pfap2 f2 x2                              // apply ap
= [] @ f1 @ x1, (flip ap) f2 x2                             // puree
= f1 @ x1, ap x2 f2                                         // simplify empty list, apply flip
= f1 @ x1, ap (x21, x22) (f21, f22)                         // expand tuples
= f1 @ x1, (f21 @ x21, f22 x22)                             // apply ap

By comparing both you can get a better understanding of why two flips are necessary.

Reasoning like this is a simple but powerful tool. We kinda do it continuously, informally, while writing code, which is usually called "running the program in your head". The absence of side-effects (i.e. pure functional programming) makes it easier to do it formally as well as informally, since you typically need to juggle less stuff in your head.

Fuchu: a functional test library for .NET

In my last two posts I showed how MbUnit supports first-class tests, and how you could use that to build a DSL in F# around it.

I explained how many concepts in typical xUnit frameworks can be more simply expressed when tests are first-class values, which is not the case for most .NET and Java test frameworks.

More concretely, test setup/teardown is a function over a test, and parameterized tests are... just data manipulation.

Since first-class tests greatly simplify things, why not dispense with the typical class-based, attribute-driven approach and build a test library around first-class tests? Well, Haskellers have been doing this for at least 10 years now, with HUnit.

HUnit organizes tests using this tree:

-- | The basic structure used to create an annotated tree of test cases. 
data Test 
    -- | A single, independent test case composed. 
    = TestCase Assertion 
    -- | A set of @Test@s sharing the same level in the hierarchy. 
    | TestList [Test] 
    -- | A name or description for a subtree of the @Test@s. 
    | TestLabel String Test 

Where Assertion is simply an alias for IO (). This is all you need to organize tests in suites and give them names.

We can trivially translate this to F# :

type TestCode = unit -> unit

type Test = 
    | TestCase of TestCode
    | TestList of Test seq
    | TestLabel of string * Test

Let's see an example:

let testA = 
    TestLabel ("testsuite A", TestList 
                         [
                            TestLabel ("test A", TestCase(fun _ -> Assert.AreEqual(4, 2+2)))
                            TestLabel ("test B", TestCase(fun _ -> Assert.AreEqual(8, 4+4)))
                         ])

It's quite verbose, but we can define the same DSL as I defined earlier for MbUnit tests, so this becomes:

let testA = 
    "testsuite A " =>> [
        "test A" => 
            fun _ -> Assert.AreEqual(4, 2+2)
        "test B" =>
            fun _ -> Assert.AreEqual(8, 4+4)
    ]

Actually, I first ported HUnit (including this DSL), then discovered that MbUnit has first-class tests and later wrote the DSL around MbUnit. Everything I described in those posts (setup/teardown as higher-order functions, parameterized tests as simple data manipulation, arbitrary nesting of test suites) applies here in the exact same way.

In fact, MbUnit's class hierarchy of Test/TestSuite/TestCase can be read as the following algebraic data type:

type Test =
| TestSuite of string * Test list
| TestCase of string * Action

which turns out to be very similar to the tree we translated from HUnit, only the names are embedded instead of being a separate case.

I called this HUnit port Fuchu (it doesn't mean anything), it's on github.

Assertions

Fuchu doesn't include any assertion functions, or at least not yet. (EDIT: assertions were added in 0.2.0) It only gives you tools to organize and run tests, but you're free to use NUnit, MbUnit, xUnit, NHamcrest, etc, or more F#-ish solutions like Unquote or FsUnit or NaturalSpec for assertions.

Tighter integration with FsCheck is planned. (EDIT: it was added in the first release of Fuchu)

Runner/Tooling

As with HUnit, the test assembly is the runner itself. That is, as opposed to having an external test runner as with most test frameworks, your test assembly is an executable (a console application). This is because it's more of a library instead of a framework. As a consequence, there is no need of installing any external tool to run tests (just hit CTRL-F5 in Visual Studio) or debug tests (just set your breakpoints and hit F5 in Visual Studio). Here's a clear signal of why this matters:

How does one run a #fsharp unit test project in #vs11?

— Community for F# (@c4fsharp) March 23, 2012

So how do you run tests with Fuchu? Given a test suite testA like the one defined above, you can run it like this:

[<EntryPoint>]
let main _ = run testA // or runParallel

But this is quite inconvenient, as it's common to split tests among different modules/files and this would mean having to list all tests somewhere, to feed them to the run function. HUnit works around this using Template Haskell, and OUnit (OCaml's port of HUnit) users generate the boilerplate code by parsing the tests' source code.

In .NET we can just decorate the tests with an attribute and then use reflection to fetch them:

[<Tests>]
let testA = 
    "2+2=4" => 
        fun _ -> Assert.AreEqual(4, 2+2)

[<Tests>]
let testB = 
    "2*3=6" => 
        fun _ -> Assert.AreEqual(7, 2*3)

[<EntryPoint>]
let main args = defaultMainThisAssembly args

This function defaultMainThisAssembly does exactly what it says on the tin. Notice that it also takes the command-line args, so if you call it with "/m" it will run the tests in parallel. (Curiously, you can't say let main = defaultMainThisAssembly, it won't be recognized as the entry point).

By the way, this is just an example, you wouldn't normally annotate every single test with the Tests attribute, only the top-level test group per module.

Run this code and you get an output like this:

2*3=6: Failed: 
  Expected: 7
  But was:  6

  G:\prg\Test.fs(15,1): SomeModule.testB@15.Invoke(Unit _arg1)
 (00:00:00.0017681)

2 tests run: 1 passed, 0 ignored, 1 failed, 0 errored (00:00:00.0058780)

If you run this within Visual Studio with F5 you can navigate to the failing assertion by clicking on the line that looks like a mini stack trace.

REPL it!

Since running tests is as easy as saying "run test", it's also convenient sometimes to do so from the F# REPL.

Pros:

• You can directly load the source code under tests in the REPL, which cuts down compilation times.
• Easy to cherry-pick one or a few tests to run instead of running all tests (with the provided Test.filter function)

Cons:

• Having to manually load all dependencies to the tests. It may be possible to work around this using a variant of this script by Gustavo Guerra.
• If you reference the assembly under test in the REPL, fsi.exe blocks the DLLs, so you have to reset the REPL session to recompile. But if you're testing F# code, you can work around this by loading source code instead of referencing the assembly.

You can see an example of running tests from the REPL here.

Other tools

Integrating with other tools is not simple. Most tools out there seem to assume that tests are organized in classes, and each test corresponds to a method or function. This also happens with MbUnit's StaticTestFactory: for example in ReSharper or TestDriven.Net you can't single out tests. Still, they can be made to run let-bound tests (which may be a test suite), so it should be possible to have some support within this limitation.

Also, no immediate support for any continuous test runner. I checked with Greg Young, he tells me that MightyMoose/AutoTest.NET can be configured to use an arbitrary executable (with limitations). Remco Mulder, of NCrunch, suggested wrapping the test runner in a test from a known test framework as a workaround. Maybe executing the tests after compilation (with a simple AfterBuild msbuild target) is enough. I haven't looked into this yet.

Coverage tools should have no problem, it makes no difference where the executable comes from.

Build tools should have no issues either; obviously FAKE is the more direct option, but I see no problems integrating this with other build tools.

C# support

I threw in a few wrapper functions to make this library usable in C# / VB.NET. Of course, it will never be as concise as F#, but still usable. I'm not going to fully explain this (it's just boring sugar) but you can see an example here.

NUnit/MbUnit test loading

Even though it may seem very different, Fuchu is still built on xUnit concepts. And since tests are first-class values, it's very easy to map tests written with other xUnit framework to Fuchu tests. For example, building Fuchu tests from NUnit test classes takes less than 100 LoC (it's already built into Fuchu)

This lets you use Fuchu as a runner for existing tests, and to write new tests. I'm planning to use this soon in SolrNet to replace Gallio (for example, Gallio doesn't work on Mono).

There is a limitation here: Fuchu can't express TestFixtureTearDowns. It can do TestFixtureSetups (and obviously SetUp/TearDown, as explained in previous posts), but not TestFixtureTearDowns (or at least not unless you treat that test suite separately). Give it a try and see for yourself :) . Is it a real downside? I don't think so (for example, TestFixtureTearDowns make parallelization harder), but it's something to be aware of. Also I haven't looked into test inheritance yet, but it should be pretty easy to support it.

Conclusions

Does .NET really need yet another test framework? Absolutely not. The current test frameworks are "good enough" and hugely popular. But since they don't treat tests as first-class values, extending them results in more and more complexity. Consider the lifecycle of a test in a typical unit testing framework. Inheritance and multiple marker attributes make it so complex that it reminds me of the ASP.NET page lifecycle. 

What I propose with Fuchu is a hopefully simpler, no-magic model. Remember KISS?

Code is here. Binaries on NuGet.

An example of applicative validation in FSharpx

I recently found a nice example of applicative functor validation in Scala (using Scalaz) by Chris Marshall, and decided to port it to F# and C# using FSharpx.

I blogged about applicative functor validation before, in F# and in C#.

When trying to port the Scala code to F# I found there were a few missing general functions in FSharpx, notably sequence and mapM. These are one- or two-liners, I ported them from Haskell, as it's syntactically closer to F# than Scala. Hoogle is always a big help for this.

Here is the original code in Scala; here's the F# port and here's the C# port.
I'm not going to copy it here: it's 160 lines of F# and 250 lines of C#.

This example also makes for a nice comparison of these three languages (or four, if you count the implicit presence of Haskell). There are a few little differences in the ports, it's not a literal translation, but you can still see how Scala, being semantically closer to Haskell than either F# or C#, achieves more generality. As for type inference, the F# version requires almost no type annotations, while C# needs the most type annotations, and Scala is somewhere in the middle. This actually depends on what you consider a type annotation.

I chose to make Person immutable in C# to reflect more accurately the equivalent F# and Scala code, but it's not really instrumental to this example. Still, it shows how verbose it is to create a truly immutable class in C#. The C# dev team at Microsoft seems to highly value immutability, so I still have hopes that a future version of C# will improve this situation.

The ability to define custom operators in Scala and F#, like <!> or *> (an ability that C# lacks) also makes it easier to work with different ways of composing functions. FSharpx also offers 'named' versions for many of these operators, for example <!> is simply 'map' and <*> is 'ap'. Despite what some people say, I think custom operators enable better readability once you know the concepts behind them. Remember that at some point you also learned what '=', '%' and '+' mean.

In particular, the F# port shows the Kleisli composition operator >=> which I haven't seen mentioned in F# before. This operator is like the regular function composition operator >> except it works for monadic functions a -> m b. Compare the signatures for >> and >=> for Option:

(>>)  : ('a -> 'b)        -> ('b -> 'c)        -> 'a -> 'c
(>=>) : ('a -> 'b option) -> ('b -> 'c option) -> 'a -> 'c option

I'm quite pleased with the results of this port, even if I do say so myself. This example shows again that many higher concepts in functional programming commonly applied in Haskell are applicable, useful and usable in F# and even in C#. The lack of typeclasses and type constructor abstraction in .NET means some code duplication (mapM for example has to be defined for each monad), but this duplication is on the side of library code in many cases, and so client code isn't that badly affected.

Homework: port this example to Gustavo's fork of FSharpx.

Encoding algebraic data types in C#

Algebraic data types are generally not directly expressible in C#, but they're a tool far too useful to be left unused. ADTs are a very precise modeling tool, helping making illegal states unrepresentable. The Base Class library already includes a Tuple type representing the anonymous product type, and C# also has anonymous types to represent labeled product types (isn't that confusing). And of course you could even consider simple classes or structs to be product types.

But the BCL doesn't include any anonymous sum type. We can use F#'s Choice type in C#, for example this discriminated union type in F# (borrowed from MSDN):

type Shape =
  // The value here is the radius.
| Circle of float
  // The values here are the height and width.
| Rectangle of double * double

Could be represented in C# as FSharpChoice<float, Tuple<double, double>> . But this obviously loses the labels (Circle, Rectangle). These "labels" are usually called "constructors".

A reasonable approach to encode ADTs in C# would be using ILSpy to reverse engineer the code the F# compiler generates from the discriminated union above: (this might hurt a bit, but don't get scared!)

using Microsoft.FSharp.Core;
using System;
using System.Collections;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
[DebuggerDisplay("{__DebugDisplay(),nq}"), CompilationMapping(SourceConstructFlags.SumType)]
[Serializable]
[StructLayout(LayoutKind.Auto, CharSet = CharSet.Auto)]
public abstract class Shape : IEquatable<Program.Shape>, IStructuralEquatable, IComparable<Program.Shape>, IComparable, IStructuralComparable
{
    public static class Tags
    {
        public const int Circle = 0;
        public const int Rectangle = 1;
    }
    [DebuggerTypeProxy(typeof(Program.Shape.Circle@DebugTypeProxy)), DebuggerDisplay("{__DebugDisplay(),nq}")]
    [Serializable]
    public class Circle : Program.Shape
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated, DebuggerNonUserCode]
        internal readonly double item;
        [CompilationMapping(SourceConstructFlags.Field, 0, 0), CompilerGenerated, DebuggerNonUserCode]
        public double Item
        {
            [CompilerGenerated, DebuggerNonUserCode]
            get
            {
                return this.item;
            }
        }
        [CompilerGenerated, DebuggerNonUserCode]
        internal Circle(double item)
        {
            this.item = item;
        }
    }
    [DebuggerTypeProxy(typeof(Program.Shape.Rectangle@DebugTypeProxy)), DebuggerDisplay("{__DebugDisplay(),nq}")]
    [Serializable]
    public class Rectangle : Program.Shape
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated, DebuggerNonUserCode]
        internal readonly double item1;
        [DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated, DebuggerNonUserCode]
        internal readonly double item2;
        [CompilationMapping(SourceConstructFlags.Field, 1, 0), CompilerGenerated, DebuggerNonUserCode]
        public double Item1
        {
            [CompilerGenerated, DebuggerNonUserCode]
            get
            {
                return this.item1;
            }
        }
        [CompilationMapping(SourceConstructFlags.Field, 1, 1), CompilerGenerated, DebuggerNonUserCode]
        public double Item2
        {
            [CompilerGenerated, DebuggerNonUserCode]
            get
            {
                return this.item2;
            }
        }
        [CompilerGenerated, DebuggerNonUserCode]
        internal Rectangle(double item1, double item2)
        {
            this.item1 = item1;
            this.item2 = item2;
        }
    }
    internal class Circle@DebugTypeProxy
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated, DebuggerNonUserCode]
        internal Program.Shape.Circle _obj;
        [CompilationMapping(SourceConstructFlags.Field, 0, 0), CompilerGenerated, DebuggerNonUserCode]
        public double Item
        {
            [CompilerGenerated, DebuggerNonUserCode]
            get
            {
                return this._obj.item;
            }
        }
        [CompilerGenerated, DebuggerNonUserCode]
        public Circle@DebugTypeProxy(Program.Shape.Circle obj)
        {
            this._obj = obj;
        }
    }
    internal class Rectangle@DebugTypeProxy
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated, DebuggerNonUserCode]
        internal Program.Shape.Rectangle _obj;
        [CompilationMapping(SourceConstructFlags.Field, 1, 0), CompilerGenerated, DebuggerNonUserCode]
        public double Item1
        {
            [CompilerGenerated, DebuggerNonUserCode]
            get
            {
                return this._obj.item1;
            }
        }
        [CompilationMapping(SourceConstructFlags.Field, 1, 1), CompilerGenerated, DebuggerNonUserCode]
        public double Item2
        {
            [CompilerGenerated, DebuggerNonUserCode]
            get
            {
                return this._obj.item2;
            }
        }
        [CompilerGenerated, DebuggerNonUserCode]
        public Rectangle@DebugTypeProxy(Program.Shape.Rectangle obj)
        {
            this._obj = obj;
        }
    }
    [CompilerGenerated, DebuggerNonUserCode, DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public int Tag
    {
        [CompilerGenerated, DebuggerNonUserCode]
        get
        {
            return (!(this is Program.Shape.Rectangle)) ? 0 : 1;
        }
    }
    [CompilerGenerated, DebuggerNonUserCode, DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsRectangle
    {
        [CompilerGenerated, DebuggerNonUserCode]
        get
        {
            return this is Program.Shape.Rectangle;
        }
    }
    [CompilerGenerated, DebuggerNonUserCode, DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsCircle
    {
        [CompilerGenerated, DebuggerNonUserCode]
        get
        {
            return this is Program.Shape.Circle;
        }
    }
    [CompilerGenerated, DebuggerNonUserCode]
    internal Shape()
    {
    }
    [CompilationMapping(SourceConstructFlags.UnionCase, 1)]
    public static Program.Shape NewRectangle(double item1, double item2)
    {
        return new Program.Shape.Rectangle(item1, item2);
    }
    [CompilationMapping(SourceConstructFlags.UnionCase, 0)]
    public static Program.Shape NewCircle(double item)
    {
        return new Program.Shape.Circle(item);
    }
    [CompilerGenerated, DebuggerNonUserCode]
    internal object __DebugDisplay()
    {
        return ExtraTopLevelOperators.PrintFormatToString<FSharpFunc<Program.Shape, string>>(new PrintfFormat<FSharpFunc<Program.Shape, string>, Unit, string, string, string>("%+0.8A")).Invoke(this);
    }
    [CompilerGenerated]
    public sealed override int CompareTo(Program.Shape obj)
    {
        if (this != null)
        {
            if (obj == null)
            {
                return 1;
            }
            int num = (!(this is Program.Shape.Rectangle)) ? 0 : 1;
            int num2 = (!(obj is Program.Shape.Rectangle)) ? 0 : 1;
            if (num != num2)
            {
                return num - num2;
            }
            if (this is Program.Shape.Circle)
            {
                Program.Shape.Circle circle = (Program.Shape.Circle)this;
                Program.Shape.Circle circle2 = (Program.Shape.Circle)obj;
                IComparer genericComparer = LanguagePrimitives.GenericComparer;
                double item = circle.item;
                double item2 = circle2.item;
                if (item < item2)
                {
                    return -1;
                }
                if (item > item2)
                {
                    return 1;
                }
                if (item == item2)
                {
                    return 0;
                }
                return LanguagePrimitives.HashCompare.GenericComparisonWithComparerIntrinsic<double>(genericComparer, item, item2);
            }
            else
            {
                Program.Shape.Rectangle rectangle = (Program.Shape.Rectangle)this;
                Program.Shape.Rectangle rectangle2 = (Program.Shape.Rectangle)obj;
                IComparer genericComparer2 = LanguagePrimitives.GenericComparer;
                double item3 = rectangle.item1;
                double item4 = rectangle2.item1;
                int num3 = (item3 >= item4) ? ((item3 <= item4) ? ((item3 != item4) ? LanguagePrimitives.HashCompare.GenericComparisonWithComparerIntrinsic<double>(genericComparer2, item3, item4) : 0) : 1) : -1;
                if (num3 < 0)
                {
                    return num3;
                }
                if (num3 > 0)
                {
                    return num3;
                }
                IComparer genericComparer3 = LanguagePrimitives.GenericComparer;
                double item5 = rectangle.item2;
                double item6 = rectangle2.item2;
                if (item5 < item6)
                {
                    return -1;
                }
                if (item5 > item6)
                {
                    return 1;
                }
                if (item5 == item6)
                {
                    return 0;
                }
                return LanguagePrimitives.HashCompare.GenericComparisonWithComparerIntrinsic<double>(genericComparer3, item5, item6);
            }
        }
        else
        {
            if (obj != null)
            {
                return -1;
            }
            return 0;
        }
    }
    [CompilerGenerated]
    public sealed override int CompareTo(object obj)
    {
        return this.CompareTo((Program.Shape)obj);
    }
    [CompilerGenerated]
    public sealed override int CompareTo(object obj, IComparer comp)
    {
        Program.Shape shape = (Program.Shape)obj;
        if (this != null)
        {
            if ((Program.Shape)obj == null)
            {
                return 1;
            }
            int num = (!(this is Program.Shape.Rectangle)) ? 0 : 1;
            Program.Shape shape2 = shape;
            int num2 = (!(shape2 is Program.Shape.Rectangle)) ? 0 : 1;
            if (num != num2)
            {
                return num - num2;
            }
            if (this is Program.Shape.Circle)
            {
                Program.Shape.Circle circle = (Program.Shape.Circle)this;
                Program.Shape.Circle circle2 = (Program.Shape.Circle)shape;
                double item = circle.item;
                double item2 = circle2.item;
                if (item < item2)
                {
                    return -1;
                }
                if (item > item2)
                {
                    return 1;
                }
                if (item == item2)
                {
                    return 0;
                }
                return LanguagePrimitives.HashCompare.GenericComparisonWithComparerIntrinsic<double>(comp, item, item2);
            }
            else
            {
                Program.Shape.Rectangle rectangle = (Program.Shape.Rectangle)this;
                Program.Shape.Rectangle rectangle2 = (Program.Shape.Rectangle)shape;
                double item3 = rectangle.item1;
                double item4 = rectangle2.item1;
                int num3 = (item3 >= item4) ? ((item3 <= item4) ? ((item3 != item4) ? LanguagePrimitives.HashCompare.GenericComparisonWithComparerIntrinsic<double>(comp, item3, item4) : 0) : 1) : -1;
                if (num3 < 0)
                {
                    return num3;
                }
                if (num3 > 0)
                {
                    return num3;
                }
                double item5 = rectangle.item2;
                double item6 = rectangle2.item2;
                if (item5 < item6)
                {
                    return -1;
                }
                if (item5 > item6)
                {
                    return 1;
                }
                if (item5 == item6)
                {
                    return 0;
                }
                return LanguagePrimitives.HashCompare.GenericComparisonWithComparerIntrinsic<double>(comp, item5, item6);
            }
        }
        else
        {
            if ((Program.Shape)obj != null)
            {
                return -1;
            }
            return 0;
        }
    }
    [CompilerGenerated]
    public sealed override int GetHashCode(IEqualityComparer comp)
    {
        if (this == null)
        {
            return 0;
        }
        int num;
        if (this is Program.Shape.Circle)
        {
            Program.Shape.Circle circle = (Program.Shape.Circle)this;
            num = 0;
            return -1640531527 + (LanguagePrimitives.HashCompare.GenericHashWithComparerIntrinsic<double>(comp, circle.item) + ((num << 6) + (num >> 2)));
        }
        Program.Shape.Rectangle rectangle = (Program.Shape.Rectangle)this;
        num = 1;
        num = -1640531527 + (LanguagePrimitives.HashCompare.GenericHashWithComparerIntrinsic<double>(comp, rectangle.item2) + ((num << 6) + (num >> 2)));
        return -1640531527 + (LanguagePrimitives.HashCompare.GenericHashWithComparerIntrinsic<double>(comp, rectangle.item1) + ((num << 6) + (num >> 2)));
    }
    [CompilerGenerated]
    public sealed override int GetHashCode()
    {
        return this.GetHashCode(LanguagePrimitives.GenericEqualityComparer);
    }
    [CompilerGenerated]
    public sealed override bool Equals(object obj, IEqualityComparer comp)
    {
        if (this == null)
        {
            return obj == null;
        }
        Program.Shape shape = obj as Program.Shape;
        if (shape == null)
        {
            return false;
        }
        Program.Shape shape2 = shape;
        int num = (!(this is Program.Shape.Rectangle)) ? 0 : 1;
        Program.Shape shape3 = shape2;
        int num2 = (!(shape3 is Program.Shape.Rectangle)) ? 0 : 1;
        if (num != num2)
        {
            return false;
        }
        if (this is Program.Shape.Circle)
        {
            Program.Shape.Circle circle = (Program.Shape.Circle)this;
            Program.Shape.Circle circle2 = (Program.Shape.Circle)shape2;
            return circle.item == circle2.item;
        }
        Program.Shape.Rectangle rectangle = (Program.Shape.Rectangle)this;
        Program.Shape.Rectangle rectangle2 = (Program.Shape.Rectangle)shape2;
        return rectangle.item1 == rectangle2.item1 && rectangle.item2 == rectangle2.item2;
    }
    [CompilerGenerated]
    public sealed override bool Equals(Program.Shape obj)
    {
        if (this == null)
        {
            return obj == null;
        }
        if (obj == null)
        {
            return false;
        }
        int num = (!(this is Program.Shape.Rectangle)) ? 0 : 1;
        int num2 = (!(obj is Program.Shape.Rectangle)) ? 0 : 1;
        if (num != num2)
        {
            return false;
        }
        if (this is Program.Shape.Circle)
        {
            Program.Shape.Circle circle = (Program.Shape.Circle)this;
            Program.Shape.Circle circle2 = (Program.Shape.Circle)obj;
            double item = circle.item;
            double item2 = circle2.item;
            return (item != item && item2 != item2) || item == item2;
        }
        Program.Shape.Rectangle rectangle = (Program.Shape.Rectangle)this;
        Program.Shape.Rectangle rectangle2 = (Program.Shape.Rectangle)obj;
        double item3 = rectangle.item1;
        double item4 = rectangle2.item1;
        if ((item3 != item3 && item4 != item4) || item3 == item4)
        {
            double item5 = rectangle.item2;
            double item6 = rectangle2.item2;
            return (item5 != item5 && item6 != item6) || item5 == item6;
        }
        return false;
    }
    [CompilerGenerated]
    public sealed override bool Equals(object obj)
    {
        Program.Shape shape = obj as Program.Shape;
        return shape != null && this.Equals(shape);
    }

Whew! That's a lot of code! Let's break down some of this code:

• The DebuggerDisplay, DebuggerTypeProxy, DebuggerBrowsable, DebuggerNonUserCode attributes and DebugTypeProxy classes enhance the debugging experience.
• Discriminated union types are marked as Serializable.
• Discriminated union types implement equality and comparison (IEquatable, IComparable, IStructuralEquatable, IStructuralComparable, Equals(), GetHashCode())
• Tags (simple integer constants) are used to optimize the implementation of equality and comparison.

It seems inviable to write such an amount of code in C# every time we want an ADT. However, underneath all the attributes and noise, the gist of it is quite simple: a class hierarchy starting with an abstract class plus a concrete subclass for each case:

abstract class Shape {
    class Circle: Shape {
        public readonly float Radius;

        public Circle(float radius) {
            Radius = radius;
        }
    }

    class Rectangle: Shape {
        public readonly double Height;
        public readonly double Width;

        public Rectangle(double height, double width) {
            Height = height;
            Width = width;
        }
    }
}

Shape is abstract because the only valid cases are Circle and Rectangle. Instantiating a Shape doesn't make sense!

Now, there's a detail we have to take care of: ADTs are closed, which means that we can't add new shapes to the type without changing the Shape type itself. This is in contradiction with the general practice of OOP: if we wanted a Square we could just create a new subclass of Shape. That, however, complicates things since it makes writing total functions over Shapes harder (impossible?). For more information about this and a comparison of OO (classes/subtyping) vs FP (closed ADTs) see this Stackoverflow question. OCaml supports "open ADTs" (actually called "open variants" or "polymorphic variants") which are powerful but have their cons too.

But I digress. The goal is to prevent subclasses of Rectangle, Circle and further subclasses of Shape. We can do this by making the constructor of Shape private, and sealing Rectangle and Shape:

public abstract class Shape {
    private Shape() {}

    public sealed class Circle : Shape {
        public readonly float Radius;

        public Circle(float radius) {
            Radius = radius;
        }
    }

    public sealed class Rectangle : Shape {
        public readonly double Height;
        public readonly double Width;

        public Rectangle(double height, double width) {
            Height = height;
            Width = width;
        }
    }
}

This is also why I chose to place Circle and Rectangle as nested classes of Shape.

So far we have a general structure and constructors. But we're not done yet! Given a Shape how do we know if it's a Circle or a Rectangle? How do we get to the data (radius, height, width)?

Any red-blooded object-oriented programmer would at this point be yelling "implement a Visitor!". Languages with first-class support for ADTs like ML dialects use pattern matching instead. Continuing with the same MSDN sample, we calculate the area for a Shape:

let shape = Circle 2.0

let area =
    match shape with
    | Circle radius -> System.Math.PI * radius * radius
    | Rectangle (h, w) -> h * w

System.Console.WriteLine area

Again we open this with ILSpy and see the following C# code (I edited it a bit to remove name mangling):

Shape shape = new Circle(2.0f);
double arg_67_0;
if (shape is Shape.Rectangle)
{
    var rectangle = (Shape.Rectangle)shape;
    double w = rectangle.Width;
    double h = rectangle.Height;
    arg_67_0 = h * w;
}
else
{
    var circle = (Shape.Circle)shape;
    double radius = circle.Radius;
    arg_67_0 = 3.1415926535897931 * radius * radius;
}
Console.WriteLine(arg_67_0);

It does runtime type testing and downcasting! As it turns out, runtime type testing is faster than a vtable dispatch, and the F# compiler optimizes taking advantage of this fact. If we had more cases in the discriminated union we'd see that the F# compiler simply nests ifs to tests all cases. This is fast but it's not very practical to write such code in C#. Also, we can't statically check if the pattern match was exhaustive. What we really want is a method on Shape (we'll call it Match) that takes two functions as parameters: one to handle the Circle case, another to handle the Rectangle case.

At this point we have several alternatives. We can implement a full visitor pattern as I said earlier, or we can take advantage of the fact that it's a closed type and simply encapsulate the type testing and downcasting, like this:

public T Match<T>(Func<float, T> circle, Func<double, double, T> rectangle) {
    if (this is Circle) {
        var x = (Circle)this;
        return circle(x.Radius);
    }
    var y = (Rectangle)this;
    return rectangle(y.Width, y.Height);
}

And now we can calculate the area of a Shape like this:

Shape shape = new Shape.Circle(2.0f);
var area = shape.Match<double>(circle: radius => Math.PI * radius * radius,
                               rectangle: (width, height) => width * height);
Console.WriteLine(area);

Note how named arguments in C# 4 make this a bit more readable. Also, using the Match method ensures that we always cover all cases. Alas, the C# compiler can't infer the return type, we have to type it explicitly.

Another alternative is to pass the whole object to the handling functions instead of just its data, e.g.

public T Match<T>(Func<Circle, T> circle, Func<Rectangle, T> rectangle)

Now we have a usable algebraic data type. When compared to F#, the boilerplate required in C# is considerable and tedious, but still worth it in my opinion. However, if you also need equality and comparison you might as well just use F# instead ;-)

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.