Validating with applicative functors and LINQ

In my last post I introduced the basics of validation with applicative functors. I used a very simple example that didn't make it justice, so let's fix that now. I'll borrow a more complex example from the FluentValidation wiki:

class Address {
    public string Line1 { get; set; }
    public string Line2 { get; set; }
    public string Town { get; set; }
    public string County { get; set; }
    public string Postcode { get; set; }        
}

class Order {
    public string ProductName { get; set; }
    public decimal? Cost { get; set; }
}

class Customer {
    public int Id { get; set; }
    public string Surname { get; set; }
    public string Forename { get; set; }
    public decimal Discount { get; set; }
    public Address Address { get; set; }
    public IList<Order> Orders { get; set; }
}

In this domain, we'll do a few somewhat arbitrary validations:

• A customer's surname can't be null.
• A customer's surname can't be 'Foo'.
• An address postcode can't be null
• Address lines are optional, but content in the second line is not allowed if there is no content in the first line.
• An order's product name can't be null
• If the order's product name is valid, check that its cost is positive.

Let's do this top-down; starting with the customer:

var customer = new Customer { ... }

var result =
    from surname in NonNull(customer.Surname, "Surname can't be null")
    join surname2 in NotEqual(customer.Surname, "foo", "Surname can't be foo") on 1 equals 1
    join address in ValidateAddress(customer.Address) on 1 equals 1
    join orders in ValidateOrders(customer.Orders) on 1 equals 1
    select customer;

surname, surname2, etc, are all dummies here, we never really use them. Now we'll describe each of these functions, starting with NonNull() which is almost trivial:

static FSharpChoice<T, Errors> NonNull<T>(T value, string err) where T: class {
    if (value == null)
        return FSharpChoice.Error<T>(err);
    return FSharpChoice.Ok(value);
}

where Errors is just a type alias for FSharpList<string>, and FSharpChoice.Error() and FSharpChoice.Ok() are just less-verbose FSharpChoice constructors for this purpose.

NotEqual() is similar and, just as one would expect, validates that a value is not equal to some other value and also returns a FSharpChoice<T, Errors>

Now let's see how ValidateAddress() looks like:

static FSharpChoice<Address, Errors> ValidateAddress(Address a) {
    return from x in NonNull(a.Postcode, "Post code can't be null")
           join y in ValidateAddressLines(a) on 1 equals 1
           select a;
}

Ok, but what's in ValidateAddressLines() ?

static FSharpChoice<Address, Errors> ValidateAddressLines(Address a) {
    if (a.Line1 != null || a.Line2 == null)
        return FSharpChoice.Ok(a);
    return FSharpChoice.Error<Address>("Line1 is empty but Line2 is not");
}

Note how both NonNull() and ValidateAddressLines() use the form "if condition then ok else error". It's a pretty common pattern so let's abstract that to a higher-order function:

static Func<T, FSharpChoice<T, Errors>> Validator<T>(Predicate<T> pred, string err) {
    return x => {
        if (pred(x))
            return FSharpChoice.Ok(x);
        return FSharpChoice.Error<T>(err);
    };
}

and now we can write:

static readonly Func<Address, FSharpChoice<Address, Errors>> ValidateAddressLines =
    Validator<Address>(x => x.Line1 != null || x.Line2 == null, 
                       "Line1 is empty but Line2 is not");

Only ValidateOrders() is left to explain. Let's see first how to validate a single order, and then we'll figure out how to make that operate on a list of orders:

static FSharpChoice<Order, Errors> ValidateOrder(Order o) {
    return
        from name in NonNull(o.ProductName, "Product name can't be null")
        from cost in GreaterThan(o.Cost, 0, string.Format("Cost for product '{0}' can't be negative", name))
        select o;
}

Here we used monadic validation (from...from...) which, as explained before, causes the second validation to run only if the first was successful.

Now the tricky part: making this work on IEnumerable<Order>. I'll use explicit types here so you can better see what's going on in each step, and inline comments:

static FSharpChoice<IEnumerable<Order>, Errors> ValidateOrders(IEnumerable<Order> orders) {
    // first we apply the validator to all orders
    IEnumerable<FSharpChoice<Order,Errors>> validatedOrders = orders.Select(ValidateOrder);

    // now we fold (Aggregate) over the list of validated orders...
    // ...to collect all orders (or their concatenated errors) in a single FSharpChoice

    // we need first an empty list of orders in the domain of validation:
    FSharpChoice<FSharpList<Order>, Errors> zero = ListModule.Empty<Order>().PureValidate();

    // now the actual fold
    return validatedOrders
        .Aggregate(zero, 
            (FSharpChoice<FSharpList<Order>, Errors> e, FSharpChoice<Order, Errors> c) => 
                from a in e
                join b in c on 1 equals 1
                select a.Cons(b))

        // finally we need to upcast the list to match the return type
        .Select(x => (IEnumerable<Order>)x);
}

Just as before with the conditional validator, we can (and should) abstract this to a higher-order function, and then we can express ValidateOrders() as:

static Func<IEnumerable<Order>, FSharpChoice<IEnumerable<Order>, Errors>> ValidateOrders =
    EnumerableValidator<Order>(ValidateOrder);

Epilogue

Validating with applicative functors is nothing new. Haskell and Scala developers have been doing it for quite some time now.

This approach to validation is attractive because it's very simple. It all revolves around the FSharpChoice type which is one of the basic building blocks in functional programming, and a very simple type: it's either this or that, either the validated value or the list of errors.

There are no ad-hoc concepts about validation here: validators are functions returning FSharpChoice<T, Errors> . We use higher-order functions to abstract validators. Folding and mapping, to manipulate validations. Validators are composed through an applicative functor or monad. These are all very general concepts. Accidental difficulty (sometimes also called "accidental complexity") is low. The core that enables applicative functor validation can be expressed in around 30 lines of F# code. In contrast, commonly used validation libraries in .NET have lots of types representing non-generic, ad-hoc concepts, abstractions, with ad-hoc interactions. Therefore, concept count and accidental complexity are high. 

Of course, applicative functors are best expressed and understood in functional languages, but C# 3 seems to be a good enough vehicle for them. They can be expressed even in Java (the Functional Java library implements the validation applicative functor) although it's quite verbose. If you want to learn more about applicative functors, see:

• Tomas Petricek's article on applicative functors in C#
• Tony Morris' presentation on validating with applicative functors (with an example in Scala, C#, Haskell and Java)
• My own articles introducing applicative functors in F#
• Applicative Programming with Effects by Conor McBride and Ross Paterson, the original paper on applicative functors, in Haskell. They also briefly mention the application of this concept to validation.

If you found this post interesting, stay tuned: Steffen, Ryan and I are planning to create a general FP library for C# and F#, where this code would be part of said library, among many other things. In the meantime, you can find the code here.

Refactoring to monadic C# - applicative functors

In the last part of this series, we "upgraded" the Maybe monad to an Either monad in order to add error messages when parsing two integers. To recap, the code using the Either monad via LINQ looked like this:

var somethingOrError =
    from userID in FSharpOption.TryParseInt(req_userID).ToFSharpChoice("Invalid User ID")
    from id in FSharpOption.TryParseInt(req_otherID).ToFSharpChoice("Invalid ID")
    select doSomething(userID, id);

somethingOrError.Match(Console.WriteLine, setError);

That code, however, only dealt with setting one error message for the whole computation. When it got the first error, it aborted the rest of the computation.

Sometimes we do want this shortcut evaluation, but more generally, when validating data, we want to validate the whole thing, and then display a list of errors, not abort at the first error we find.

To do this, we need to step down from monads into a weaker abstraction: applicative functors. I've already blogged about applicative functors in F# and C#, mostly in the context of formlets. In a nutshell:

• Applicative functors are defined by two functions: pure and apply.
• These functions must satisfy some laws, which I won't mention here.
• Pure is basically a Func<T, M<T>> for some M, i.e. it puts some value into M
• Apply is basically a Func<M<Func<A,B>>,M<A>,M<B>>, i.e. it applies a function within M
• All monads are applicative functors (but not necessarily the other way around).
• All applicative functors are functors (but not necessarily the other way around), which means you can Select() over them with LINQ.

But I don't want to get into much detail here. What's interesting here is that we won't use the "default" implementation of the Either applicative functor (i.e. the one derived from the monad) because it would only keep the first error message, so it would be pretty useless in this case! The Either applicative functor we'll use will of course collect all validation messages in a list.

But first, for comparison, here's some simple imperative code to parse two numbers and then do something with them or display all errors:

var errors = new List<string>();

int userID;
var userID_ok = int.TryParse(req_userID, out userID);
if (!userID_ok)
    errors.Add("Invalid user ID");

int id;
var id_ok = int.TryParse(req_otherID, out id);
if (!id_ok)
    errors.Add("Invalid ID");

if (errors.Count > 0)
    setErrors(errors);
else
    Console.WriteLine(doSomething(userID, id));

Just like with CsFormlets, this Either applicative functor can be expressed either "directly", or using LINQ as explained by Tomas Petricek here. In this post I'll skip the direct syntax and use LINQ instead. And using LINQ, the above imperative code is translated into this:

var userID = FSharpOption.TryParseInt(req_userID)
    .ToFSharpChoice(FSharpList.New("Invalid User ID"));
var id = FSharpOption.TryParseInt(req_otherID)
    .ToFSharpChoice(FSharpList.New("Invalid ID"));

var result =
    from a in userID
    join b in id on 1 equals 1
    select doSomething(a, b);

result.Match(Console.WriteLine, setErrors);

Note that it's very similar to the monadic code we were first using, only instead of from...from... (which compiles to SelectMany(), i.e. monadic bind) we do from...join... .
"on 1 equals 1" is the syntactic tax we have to pay for bending LINQ like this.

result is of type FSharpChoice<int, FSharpList<string>> , that is it contains either the result of doSomething() or a list of errors.

This was a trivial example of using applicative functors for validation; just an introduction. It doesn't show one of its biggest strengths: composability. In the next post we'll look into validating a more complex domain.

Code is here.

Refactoring to monadic C# - part 2

This is a follow-up to my previous article "Refactoring to monadic C#", in which I described how to refactor a typical imperative piece of code into functional style, and introduced and applied the Maybe monad.

To quickly recap, the code I refactored was a parser for NuGet's version ranges, e.g. [1.0] or (1.0,2.0), similar to math interval notation.

It's probably a good idea to keep both part 1 and part 2 of this article open side by side for reference and comparison.

Nesting options

After the refactoring we did in part 1, the function that parsed the upper bound of the interval was:

var maxVersion = L.F((string[] parts) =>  {
    var p = parts.Length == 2 ? parts[1] : parts[0];
    if (string.IsNullOrWhiteSpace(p))
        return FSharpOption<Version>.Some(null);
    return ParseVersion(p);
});

But... isn't Some(null) kind of awkward? Aren't option types supposed to save us from nulls?

A useful thing about option types I haven't mentioned is that they can be nested, that is, unlike Nullable<T> it's perfectly valid (and useful) to have an option of an option. Using nested options the code looks like this:

var maxVersion = L.F((string[] parts) =>  {
    var p = parts.Length == 2 ? parts[1] : parts[0];
    if (string.IsNullOrWhiteSpace(p))
        return FSharpOption<FSharpOption<Version>>.Some(FSharpOption<Version>.None);
    return ParseVersion(p).Select(v => v.ToOption());
});

Of course, now we have to change the monadic code in LINQ to handle this nested option (changes in bold):

var versionRange = L.F(() => from x in checkLength(value)
                             from isMin in minInclusive(value)
                             from isMax in maxInclusive(value)
                             let val = value.Substring(1, value.Length - 2)
                             let parts = val.Split(',')
                             from y in checkParts(parts)
                             from min in minVersion(parts)
                             from max in maxVersion(parts)
                             select (IVersionSpec)new VersionSpec {
                                 IsMinInclusive = isMin, 
                                 MinVersion = min.HasValue() ? min.Value : null, 
                                 IsMaxInclusive = isMax, 
                                 MaxVersion = max.HasValue() ? max.Value : null,
                             });

In this particular case, Some(null) wasn't so bad because we're not doing anything else with that value, but more generally, if you need to further process the value, nesting options is the better, cleaner way.

Error messages

Now let's see a different but closely related example: we want to parse some values (perhaps from a web request) and show an error if any parsing fails. If the values are parsed successfully, we do "something" with them (e.g. look them up in a database or whatever).

A typical imperative solution might look like this:

int doSomething(int userID, int id) {
    // fetch some other entity, do "stuff"
    return userID + id;
}

void setError(string e) {}

const string req_userID = "123";
const string req_otherID = "999";

int userID;
var userID_ok = int.TryParse(req_userID, out userID);
if (!userID_ok) {
    setError("Invalid User ID");
} else {
    int id;
    var id_ok = int.TryParse(req_otherID, out id);
    if (!id_ok) {
        setError("Invalid ID");
    } else {
        Console.WriteLine(doSomething(userID, id));
    }
}

If you try to refactor this to Options, like the previous example, you'll quickly see that Options are not quite enough. Options contain either a value or nothing, but in this case we want something that contains either a value or an error message. Such a type is precisely called Either in Haskell. More generally, both Option (called Maybe in Haskell) and Either are sum types (also called tagged union or discriminated union). The most commonly used sum type is bool. Sum types are in turn a special case of algebraic data types.

But I digress. Back to our example, we want to map from Option to Either, by attaching the corresponding error message instead of None where the parsing fails. Just like Option, writing an Either is not hard, but since we're already using F#'s option type we might as well also use F#'s generic sum type (called Choice). C# doesn't have the notion of algebraic data types so we'll add some syntax sugar around Choice to make it more usable.

Defining a monad over Choice is trivial once you understand how the Option monad works. We only have to choose by convention that one of the branches will work as the "error" branch, and we treat it like None in Option. So when we hit an error in the computation, we skip the rest of the computation.

Once we have everything in place, we can translate the code above to:

var somethingOrError =
    from userID in FSharpOption.TryParseInt(req_userID).ToFSharpChoice("Invalid User ID")
    from id in FSharpOption.TryParseInt(req_otherID).ToFSharpChoice("Invalid ID")
    select doSomething(userID, id);

where somethingOrError is of type FSharpChoice<int,string> , that is, it contains either the result of doSomething(...) if the values were parsed correctly, or a string with the error message for the first failed parsing.

But we're not done yet! We still need to either write the result to console or call setError if something went wrong.

if (somethingOrError.IsChoice1Of2) {
    var r = (FSharpChoice<int, string>.Choice1Of2)somethingOrError;
    Console.WriteLine(r.Item);
} else {
    var r = (FSharpChoice<int, string>.Choice2Of2)somethingOrError;
    setError(r.Item);
}

Ewwww. In languages with first-class support for sum types, extracting values is done through pattern matching, not ifs and downcasting (which are leaking implementation details here). Pattern matching, as explained in the Haskell wikibook, "is a convenient way to bind variables to different parts of a given value".

Of course, we don't have pattern matching in C#, but we can easily write an ad-hoc match, by abstracting the actions from the last snippet, so we can now write:

somethingOrError.Match(Console.WriteLine, setError);

Much cleaner, and it also ensures that both branches are covered.

More generic pattern matching can be encoded in C# (there are numerous examples on the web) but it's just too awkward, complex, unwieldy for my taste.

Conclusion

Even though C# lacks first-class support for sum types and pattern matching, they can still be gainfully encoded and used. Using FSharpChoice for sum types is convenient because it already implements equality semantics and you only have to wrap pattern matching once.

Of course, it's not without downsides: FSharpChoice is esentially an anonymous sum type (Choice1Of2 and Choice2Of2 have no real meaning), so you can't tell one FSharpChoice<int,int> from another FSharpChoice<int,int>, even though they may be representing widely different things. Also, as you add more "choices" to the type, it gets increasingly unwieldy, i.e. what does the third type represent in a FSharpChoice<int,string,int,bool> ? Without the ability to name things you have to keep track of this in your head (or add suitable functions, at the cost of convenience and conciseness). However, as shown in this post, the two-type generic Choice is quite simple and useful.

As with the first part of this post, I specifically tried to avoid getting into too much detail about the implementation or how it works under the covers, instead focusing on the end result, at the cost of some handwaving. You can see the entire implementation (it's almost trivial really) on github.

Refactoring to monadic C#

You may have heard or read that LINQ is more than just queries, that it's actually syntax sugar for monadic code. But unless you previously used monads in another language with better, more explicit support (like Haskell or F#) you might not grok the concept of monads or how exactly monads are useful in real-world code.

No, this is not yet another monad tutorial. Instead, I'll show how a concrete function in a real-world C# project can be refactored to take advantage of a monad. But I'm not going to explain how this monad works or how it's implemented.

First, a warning: there is quite a bit of code in this post. It's simple code, but I recommend really reading it and not just skimping over it to understand what's going on.

The code we'll work with is a simple utility function that parses version ranges in NuGet, used to express dependency versions. For example, the string "2.1" indicates version 2.1. Another example: "[2.0,2.5]" is an interval between versions 2.0 and 2.5, inclusive. You can find the full specification here.

This post is not a criticism of NuGet or its code, or even imperative programming. There's nothing "wrong" here. I was just browsing NuGet's code and thought this would make a good example on how to refactor imperative code to functional, monadic style. It's a decidedly different style, but I'll leave it to you to decide if it's better or not. In my experience, shoving functional programming down programmers' throats doesn't work. People have to see and decide for themselves.

The code we'll refactor can be found here in NuGet's repository. I'll copy it here for convenience:

public static bool TryParseVersionSpec(string value, out IVersionSpec result) {
    if (value == null) {
        throw new ArgumentNullException("value");
    }

    var versionSpec = new VersionSpec();
    value = value.Trim();

    // First, try to parse it as a plain version string 
    Version version;
    if (Version.TryParse(value, out version)) {
        // A plain version is treated as an inclusive minimum range 
        result = new VersionSpec {
            MinVersion = version,
            IsMinInclusive = true
        };

        return true;
    }

    // It's not a plain version, so it must be using the bracket arithmetic range syntax

    result = null;

    // Fail early if the string is too short to be valid 
    if (value.Length < 3) {
        return false;
    }

    // The first character must be [ ot ( 
    switch (value.First()) {
        case '[':
            versionSpec.IsMinInclusive = true;
            break;
        case '(':
            versionSpec.IsMinInclusive = false;
            break;
        default:
            return false;
    }

    // The last character must be ] ot ) 
    switch (value.Last()) {
        case ']':
            versionSpec.IsMaxInclusive = true;
            break;
        case ')':
            versionSpec.IsMaxInclusive = false;
            break;
        default:
            return false;
    }

    // Get rid of the two brackets 
    value = value.Substring(1, value.Length - 2);

    // Split by comma, and make sure we don't get more than two pieces 
    string[] parts = value.Split(',');
    if (parts.Length > 2) {
        return false;
    }

    // If there is only one piece, we use it for both min and max 
    string minVersionString = parts[0];
    string maxVersionString = (parts.Length == 2) ? parts[1] : parts[0];

    // Only parse the min version if it's non-empty 
    if (!String.IsNullOrWhiteSpace(minVersionString)) {
        if (!Version.TryParse(minVersionString, out version)) {
            return false;
        }
        versionSpec.MinVersion = version;
    }

    // Same deal for max 
    if (!String.IsNullOrWhiteSpace(maxVersionString)) {
        if (!Version.TryParse(maxVersionString, out version)) {
            return false;
        }
        versionSpec.MaxVersion = version;
    }

    // Successful parse! 
    result = versionSpec;
    return true;
}

Going functional

Let's start refactoring. The first thing we should note is that by functional standards this is a pretty monolithical function. In functional programming we tend to write very little functions instead, sometimes even trivial, and avoiding state as much as possible, then compose them to achieve the end result.

In this case, we can identify several functions:

• Check input length
• Parse interval start inclusiveness
• Parse interval end inclusiveness
• Check interval syntax
• Parse lower bound version
• Parse upper bound version

In order to make these functions composable, we'll avoid using out parameters. We could do this by making them return a Tuple<bool,T> where the bool represents if the function was successful or not, and T is the type of the actual result. For example, we could wrap Version.TryParse like this:

Tuple<bool, Version> ParseVersion(string value) {
    Version v;
    var ok = Version.TryParse(value, out v);
    if (ok)
        return Tuple.Create(true, v);
    return Tuple.Create(false, v);
}

In fact F# does this automatically for you. But we can do better by using an option type. An option type is similar to the familiar Nullable<T> type: we can ask if it contains a value or not, and if it does have a value we can retrieve it. The difference is that an option type works for any underlying type, not just value types.

It's not hard to implement a basic option type, but F# already has a proper implementation, and if you have Visual Studio 2010 you already have F#. If you don't, get F# here. So we'll just reference FSharp.Core.dll and use F#'s option type. With a couple of extension methods to ease the syntax in C#, ParseVersion can be written as:

FSharpOption<Version> ParseVersion(string value) {
    Version v;
    var ok = Version.TryParse(value, out v);
    if (ok)
        return v.ToOption();
    return FSharpOption<Version>.None;
}

At this point you may ask why not just return null when value is not a valid version. Yes, we could do that in this particular case, but we'll see that sometimes null can be valid value to return, and then we wouldn't be able to tell an invalid value from a valid null value.

Using FSharpOption<T> the signature of the main function:

bool TryParseVersionSpec(string value, out IVersionSpec result)

becomes:

FSharpOption<IVersionSpec> ParseVersionSpec(string value)

Now let's start implementing one by one the functions in the bulleted list above. I'll write them as local Funcs, but you could just as well make them regular methods if you prefer.

var checkLength = L.F((string val) => val.Length < 3 ? FSharpOption<Unit>.None : FSharpOption.SomeUnit);

L.F() is a little function to help C# with type inference of Funcs, as described here, so checkLength is of type Func<string, FSharpOption<Unit>>

Unit is like void. It means "nothing", but unlike void, it's an actual type we can use, so we can write FSharpOption<Unit> (C# won't allow FSharpOption<Void>). FSharpOption<Unit> has only two possible values: None and Some(null) (represented by SomeUnit)

The rest of the functions look like this:

var minInclusive = L.F((string val) => {
    var c = val.First();
    if (c == '[')
        return true.ToOption();
    if (c == '(')
        return false.ToOption();
    return FSharpOption<bool>.None;
});
var maxInclusive = L.F((string val) => {
    var c = val.Last();
    if (c == ']')
        return true.ToOption();
    if (c == ')')
        return false.ToOption();
    return FSharpOption<bool>.None;
});
var checkParts = L.F((string[] parts) => parts.Length > 2 ? FSharpOption<Unit>.None : FSharpOption.SomeUnit);
var minVersion = L.F((string[] parts) => {
    if (string.IsNullOrWhiteSpace(parts[0]))
        return FSharpOption<Version>.Some(null);
    return ParseVersion(parts[0]);
});
var maxVersion = L.F((string[] parts) =>  {
    var p = parts.Length == 2 ? parts[1] : parts[0];
    if (string.IsNullOrWhiteSpace(p))
        return FSharpOption<Version>.Some(null);
    return ParseVersion(p);
});

So far we've only defined a bunch of functions but haven't done anything with the actual input. Here's the actual processing:

var singleVersion = ParseVersion(value);
if (singleVersion.HasValue())
    return ((IVersionSpec)new VersionSpec { IsMinInclusive = true, MinVersion = singleVersion.Value }).ToOption();

if (!checkLength(value).HasValue())
    return FSharpOption<IVersionSpec>.None;
var isMin = minInclusive(value);
if (!isMin.HasValue())
    return FSharpOption<IVersionSpec>.None;
var isMax = maxInclusive(value);
if (!isMax.HasValue())
    return FSharpOption<IVersionSpec>.None;
var svalue = value.Substring(1, value.Length - 2);
var sparts = svalue.Split(',');
var min = minVersion(sparts);
if (!min.HasValue())
    return FSharpOption<IVersionSpec>.None;
var max = maxVersion(sparts);
if (!max.HasValue())
    return FSharpOption<IVersionSpec>.None;
return ((IVersionSpec)new VersionSpec { IsMinInclusive = isMin.Value, MinVersion = min.Value, IsMaxInclusive = isMax.Value, MaxVersion = max.Value }).ToOption();

What have we really achieved so far, compared to the original imperative solution? We encapsulated all parsing and checking into neat little referentially transparent functions. There's no mutability or side-effects here, whereas in the imperative code the VersionSpec instance gets mutated along the entire function. It might not seem like much in this little example, but once you become reference-transparency aware (and you apply this awareness) your code gets easier to understand and compose, just as Wes describes.

Since VersionSpec is no longer mutated, we could also just ditch IVersionSpec (the readonly interface to VersionSpec) and make VersionSpec truly immutable.

Further modifications and monadifications

But we still have some significant cruft left: all that if (!something.HasValue()) return FSharpOption<IVersionSpec>.None isn't very pretty. Here's where the monad comes in, and another reason to use option types. FSharp.Core.dll already defines a monad around FSharpOption (called the Maybe monad). All we have to do is wrap the functions that implement this into the extension methods that C# requires to enable LINQ syntax sugar (or just implement it directly, it's pretty trivial code), and then we can write that last code block as:

var singleVersion =
    from v in ParseVersion(value)
    select (IVersionSpec)new VersionSpec { IsMinInclusive = true, MinVersion = v };

var versionRange = L.F(() => {
    return from x in checkLength(value)
           from isMin in minInclusive(value)
           from isMax in maxInclusive(value)
           let val = value.Substring(1, value.Length - 2)
           let parts = val.Split(',')
           from y in checkParts(parts)
           from min in minVersion(parts)
           from max in maxVersion(parts)
           select (IVersionSpec)new VersionSpec { IsMinInclusive = isMin, MinVersion = min, IsMaxInclusive = isMax, MaxVersion = max };
});

return singleVersion.OrElse(versionRange)();

By now you're probably thinking "I could have done something similar!". Indeed, you could have invented monads, and you probably have, except that maybe you didn't know you were doing monads so you couldn't take full advantage of the power of this abstraction.

If I got you interested in functional programming and monads, my job here is done. I hope this refactoring was detailed enough to compare the functional and imperative ways of thinking, and also to demystify monads. If you want to learn more about monads, use a language with better syntactic support, like Haskell or F#. Monads don't really require any special language support (you can write and use monads in Java, Python, Ruby, Perl, ...), but without syntax sugar they are harder to read and write, at least until you're comfortable with them. In F# this syntax sugar is called computation expressions, in Haskell do notation.

Desugaring the LINQ expression above into extension methods is a good way to understand what the LINQ syntax does under the covers and see how the functions are composed.

By the way, this is not the only way to apply monads to parsing. We could have used monadic parser combinators, which can provide automatic parsing error messages, but it's a whole different approach from the get-go, not so easily refactorable from existing imperative code. If you're interested, there are some implementations of parser combinators in C#, check out Sprache or RxParsers.

All code shown here (plus the parts I didn't show) is available on github.

All code copied from NuGet is copyrighted by the Outercurve Foundation, licensed under the Apache License, Version 2.0

Formlets in C# and VB.NET

All this talk about formlets in F#, by now you might think this is something that only works in functional languages. Nothing further from the truth. Tomáš Petříček has already blogged about formlets in C#, and I've been working on a wrapper around FsFormlets to be used in C# and VB.NET I called CsFormlets (I'm really good with names if you haven't noticed).

In this post I'll assume you already know about formlets. If you don't, I recommend reading Tomas' article. If you want to know more about my particular implementation of formlets, see my previous posts on the subject. If you're just too lazy to read all those lengthy articles, that's ok, read on, you'll still get a good feeling of formlets.

So if F# is a first-class .NET language, why is it necessary to wrap FsFormlets for C# consumption? Well, for one the formlet type is utterly unmanageable in C#. The formlet type in FsFormlets is (expressed in F#):

type 'a Formlet = 'a Error ErrorList XmlWriter Environ XmlWriter NameGen

where Error, ErrorList, etc, each are individual applicative functors. Type aliases in F# make it easy to hide the 'real' type underneath that, but unfortunately, C# doesn't support type aliases with type parameters, so the formlet type becomes this monster:

FSharpFunc<int, Tuple<Tuple<FSharpList<XNode>, FSharpFunc<FSharpList<Tuple<string, InputValue>>, Tuple<FSharpList<XNode>, Tuple<FSharpList<string>, FSharpOption<T>>>>>, int>>

And no, you can't always var your way out, so to keep this usable I wrapped this in a simpler Formlet<T> type.

Functions that use F# types like FSharpFunc<...> (obviously) and FSharpList<Tuple<T,U>> are wrapped so they use System.Func<...> and IEnumerable<KeyValuePair<T,U>> respectively. F# options are converted to/from nullables whenever possible. Extension methods are provided to work more easily with F# lists and option types. Active patterns (used in F# to match success or failure of formlet) are just not available. Also, applicative operators like <*>, <*, etc are just not accessible in C#, so I wrapped them in methods of Formlet<T>. This yields a fluent interface, as we'll see in a moment.

As usual, I'll demo the code with a concrete form, which looks like this:

As I wanted to make this example more real-world than previous ones, I modeled it after the signup form of a real website, don't remember which one but it doesn't really matter. This time it even has decent formatting and styling!

As usual we'll build the form bottom-up.

Password

First the code to collect the password:

static readonly FormElements e = new FormElements();

static readonly Formlet<string> password = 
    Formlet.Tuple2<string, string>() 
        .Ap(e.Password(required: true).WithLabelRaw("Password <em>(6 characters or longer)</em>")) 
        .Ap(e.Password(required: true).WithLabelRaw("Enter password again <em>(for confirmation)</em>")) 
        .SatisfiesBr(t => t.Item1 == t.Item2, "Passwords don't match") 
        .Select(t => t.Item1) 
        .SatisfiesBr(t => t.Length >= 6, "Password must be 6 characters or longer");

Formlet.Tuple2 is just like "yields t2" in FsFormlets, i.e. it sets up a formlet to collect two values in a tuple. Unfortunately, type inference is not so good in C# so we have to define the types here. We'll see later some alternatives to this.

Ap() is just like <*> in FsFormlets.

SatisfiesBr() applies validation. Why "Br"? Because it outputs a <br/> before writing the error message. If no <br/> was present, the error "Password must be 6 characters or longer" would overflow and show in two lines, which looks bad.
This is defined as a simple extension method, implemented using the built-in Satisfies():

static IEnumerable<XNode> BrError(string err, List<XNode> xml) { 
    return xml.Append(X.E("br"), X.E("span", X.A("class", "error"), err)); 
}

static Formlet<T> SatisfiesBr<T>(this Formlet<T> f, Func<T, bool> pred, string error) { 
    return f.Satisfies(pred, 
        (_, x) => BrError(error, x), 
        _ => new[] { error }); 
}

Now you may be wondering about X.E() and X.A(). They're just simple functions to build System.Xml.Linq.XElements and XAttributes respectively.

Back to the password formlet: ever since C# 3.0, Select() is the standard name in C# for what is generally known as map, so I honor that convention in CsFormlets. In this case, it's used to discard the second collected value, since password equality has already been tested in the line above.

Account URL

Moving on, the formlet that collects the account URL:

static readonly Formlet<string> account = 
    Formlet.Single<string>() 
        .Ap("http://") 
        .Ap(e.Text(attributes: new AttrDict {{"required","required"}})) 
        .Ap(".example.com") 
        .Ap(X.E("div", X.Raw("Example: http://<b>company</b>.example.com"))) 
        .Satisfies(a => !string.IsNullOrWhiteSpace(a), "Required field") 
        .Satisfies(a => a.Length >= 2, "Two characters minimum") 
        .Satisfies(a => string.Format("http://{0}.example.com", a).IsUrl(), "Invalid account") 
        .WrapWith(X.E("fieldset"));

You should notice at least two weird things here. If you don't, you're not paying attention! :-)

First weird thing: I said Ap() is <*> , but you couldn't apply <*> to pure text (.Ap("http://")) or XML as shown here, only to a formlet! This is one of the advantages of C#: Ap() is overloaded to accept text and XML, in which case it lifts them to Formlet<Unit> and then applies <*
Because of these overloads Ap() could almost be thought of as append instead of apply.

Second weird thing: instead of writing e.Text(required: true) as in the password formlet, I explicitly used required just as HTML attribute. However, requiredness is checked server-side after all markup. This is for the same reason I defined SatisfiesBr() above: we wouldn't like the error message to show up directly after the input like this:

http:// Required field.example.com

Alternatively, I could have used a polyfill for browsers that don't support the required attribute, but I'm going for a zero-javascript solution here, and also wanted to show this flexibility.

It's also possible to define default conventions for all error messages in formlets (i.e. always show errors above the input, or below, or as balloons) but I won't show it here.

Oh, in case it's not evident, X.Raw() parses XML into System.Xml.Linq.XNodes.

User

Let's put things together in a User class

static readonly Formlet<User> user = 
    Formlet.Tuple5<string, string, string, string, string>() 
        .Ap(e.Text(required: true).WithLabel("First name")) 
        .Ap(e.Text(required: true).WithLabel("Last name")) 
        .Ap(e.Email(required: true).WithLabelRaw("Email address <em>(you'll use this to sign in)</em>")) 
        .Ap(password) 
        .WrapWith(X.E("fieldset")) 
        .Ap(X.E("h3", "Profile URL")) 
        .Ap(account) 
        .Select(t => new User(t.Item1, t.Item2, t.Item3, t.Item4, t.Item5));

Nothing new here, just composing the password and account URL formlets along with a couple other inputs, yielding a User.

Card expiration

Let's tackle the last part of the form, starting with the credit card expiration:

static Formlet<DateTime> CardExpiration() { 
    var now = DateTime.Now; 
    var year = now.Year; 
    return Formlet.Tuple2<int, int>() 
        .Ap(e.Select(now.Month, Enumerable.Range(1, 12))) 
        .Ap(e.Select(year, Enumerable.Range(year, 10))) 
        .Select(t => new DateTime(t.Item2, t.Item1, 1).AddMonths(1)) 
        .Satisfies(t => t > now, t => string.Format("Card expired {0:#} days ago!", (now-t).TotalDays)) 
        .WrapWithLabel("Expiration date<br/>"); 
}

This formlet, unlike previous ones, is a function, because it depends on the current date. It has two <select/> elements: one for the month, one for the year, by default set to the current date.

Billing info

Now we use the card expiration formlet in the formlet that collects other billing data:

static readonly IValidationFunctions brValidationFunctions = 
    new Validate(new ValidatorBuilder(BrError));

static Formlet<BillingInfo> Billing() { 
    return Formlet.Tuple4<string, DateTime, string, string>() 
        .Ap(e.Text(required: true).Transform(brValidationFunctions.CreditCard).WithLabel("Credit card number")) 
        .Ap(CardExpiration()) 
        .Ap(e.Text(required: true).WithLabel("Security code")) 
        .Ap(e.Text(required: true).WithLabelRaw("Billing ZIP <em>(postal code if outside the USA)</em>")) 
        .Select(t => new BillingInfo(t.Item1, t.Item2, t.Item3, t.Item4)) 
        .WrapWith(X.E("fieldset")); 
}

Transform() is just a simple function application. brValidationFunctions.CreditCard is a function that applies credit card number validation (the Luhn algorithm). The validation function is initialized with the same BrError() convention I defined above, i.e. it writes a <br/> and then the error message.

Top formlet

Here's the top-level formlet, the one we'll use in the controller to show the entire form and collect all values:

static Formlet<RegistrationInfo> IndexFormlet() { 
    return Formlet.Tuple2<User, BillingInfo>() 
        .Ap(X.E("h3", "Enter your details")) 
        .Ap(user) 
        .Ap(X.E("h3", "Billing information")) 
        .Ap(Billing()) 
        .Select(t => new RegistrationInfo(t.Item1, t.Item2)); 
}

LINQ & stuff

I've been using Formlet.Tuple in these examples, but you could also use Formlet.Yield, which behaves just like "yields" in FsFormlets. In F# this is no problem because functions are curried, but this is not the case in C#. Even worse, type inference is really lacking in C# compared to F#. This makes Formlet.Yield quite unpleasant to use:

Formlet.Yield<Func<User,Func<BillingInfo,RegistrationInfo>>>((User a) => (BillingInfo b) => new RegistrationInfo(a,b))

With a little function to help with inference such as this one, it becomes

Formlet.Yield(L.F((User a) => L.F((BillingInfo b) => new RegistrationInfo(a, b))))

Still not very pretty, so I prefer to use Formlet.Tuple and then project the tuple to the desired type.

Another way to define formlets in CsFormlets is using LINQ syntax. Tomas explained in detail how this works in a recent blog post. For example, the last formlet defined with LINQ:

static Formlet<RegistrationInfo> IndexFormletLINQ() { 
    return from x in Formlet.Raw(X.E("h3", "Enter your details")) 
           join u in user on 1 equals 1 
           join y in Formlet.Raw(X.E("h3", "Billing information")) on 1 equals 1 
           join billing in Billing() on 1 equals 1 
           select new RegistrationInfo(u, billing); 
}

Also, where can be used to apply validation, although you can't define the error message in each case or where it will be displayed.

The LINQ syntax has some pros and cons.

Pros

• Less type annotations required.
• No need to define at the start of the formlet what values and types we will collect.

Cons

• join and on 1 equals 1 look somewhat odd.
• Pure text and XML need to be explicitly lifted.
• Less flexible than chaining methods. If you use where to apply validation, you can't define the message. If you want to use Satisfies(), WrapWith() or any other extension method, you have break up the formlet expression.

Personally, I prefer chaining methods over LINQ, but having a choice might come in handy sometimes.

VB.NET

The title of this post is "Formlets in C# and VB.NET", so what is really different in VB.NET? We could, of course, translate everything in this post directly to VB.NET. But VB.NET has a distinctive feature that is very useful for formlets: XML literals. Instead of:

(C#) xml.Append(X.E("br"), X.E("span", X.A("class", "error"), err));

In VB.NET we can write:

(VB.NET) xml.Append(<br/>, <span class="error"><%= err %></span>)

which is not only clearer, but also more type-safe: you can't write something like <span 112="error">, it's a compile-time error.

To be continued...

This post is too long already so I'll leave ASP.NET MVC integration and testing for another post. If you want to play with the bits, the CsFormlets code is here. All code shown here is part of the CsFormlets sample app. Keep in mind that you also need FsFormlets, which is included as a git submodule, so after cloning CsFormlets you have to init the submodules.

Enumerable.Skip vs Seq.skip

If you're an F# newbie like me^(*) you'll eventually try to use Seq.skip and Seq.take to implement pagination, just like you used Enumerable.Skip and Enumerable.Take (or a IQueryable implementation of them) in C#.

And more sooner than later you find out that they don't behave quite the same. If you haven't realized this yet, read on.

Load up fsi.

> let a = seq { 1..100 };;

An F# seq is a System.IEnumerable, it's just a convenient alias. In C# this would be expressed as:

var a = Enumerable.Range(1, 100);

Now let's paginate that. Assuming a page size of 40 elements, in C# we would do something like this:

var firstPage = a.Skip(0).Take(40).ToArray();
var lastPage = a.Skip(80).Take(40).ToArray();

Now in F# :

> let firstPage = a |> Seq.skip 0 |> Seq.take 40 |> Seq.toArray;;
> let lastPage = a |> Seq.skip 80 |> Seq.take 40 |> Seq.toArray;;

Uh-oh. The last expression throws a System.InvalidOperationException: The input sequence has an insufficient number of elements.

The thing is, Seq.skip and Seq.take are more strict and actually do bounds checking, whereas Enumerable.Skip and Enumerable.Take are more "tolerant" and may process and return fewer items than requested.

So how can we get Enumerable.Skip's behavior? The simplest option would be using it as in C#, e.g.:

> open System.Linq;;
> let lastPage = a.Skip(80).Take(40).ToArray();;

This works, but extension methods are generally not idiomatic in F#. We prefer function piping, currying and composition. So let's wrap them in curried forms, which is trivial:

> let eSkip n sequence = Enumerable.Skip(sequence, n);;
> let eTake n sequence = Enumerable.Take(sequence, n);;

And now we can operate as usual with pipes:

> let lastPage = a |> eSkip 80 |> eTake 40 |> Seq.toArray;;

By the way, F# already defines Seq.truncate which works like Enumerable.Take, so we can drop eTake and just write:

> let lastPage = a |> eSkip 80 |> Seq.truncate 40 |> Seq.toArray;;

---

(*) I've been learning F# and functional programming for about two years now, yet I still consider myself somewhat of a newbie about it... at least until I learn Haskell :-)

CRUD API for Google Spreadsheets

For a little project I'm coding, I needed to programatically post new rows to a Google spreadsheet. Luckily, there are .NET bindings to the Google Data APIs. But they're still too low-level if you want to use the spreadsheet as a database. I looked around the source repo for awhile and found this little gem in python. In the words of its creator, it helps:

Make the Google Documents API feel more like using a database.

This module contains a client and other classes which make working with the
Google Documents List Data API and the Google Spreadsheets Data API look a
bit more like working with a heirarchical database. Using the DatabaseClient,
you can create or find spreadsheets and use them like a database, with
worksheets representing tables and rows representing records.

Just what I needed! So I ported it to .net, and here is the result. The biggest difference with the python version is that tables in .net are strongly typed. When you define a Table<Entity>, the Entity's public properties are serialized when posting to the spreadsheet.

The sample app is pretty much self-explanatory. You can do CRUD operations on the rows stored on a worksheet. The structured query operators are limited, but I didn't need more. I even threw in a LINQ provider (base classes courtesy of Matt Warren), so you can do strongly typed queries:

class Entity {
  public int Amount { get; set; }
}
...
Table<Entity> t = ...
var rows = from e in t.AsQueryable()
           where e.Amount == 5
           select e;

It's still a bit rough around the edges, but usable.

UPDATE 11/03/2010: released GDataDB 0.2

Y-combinator and LINQ

Today I finally found an excuse to use Wes Dyer's implementation of the Y-combinator in C#:

public delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r)
 
 public static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f) {
     Recursive<A, R> rec = r => a => f(r(r))(a);
     return rec(rec);
 } 

I used it to recursively get all the files in a given directory, in a one-liner:

var RecGetFiles = Y<string, IEnumerable<string>>(f => d => Directory.GetFiles(d).Concat(Directory.GetDirectories(d).SelectMany(f)))

Nice, isn't it? Sample usage:

foreach (var f in RecGetFiles(Directory.GetCurrentDirectory()))
     Console.WriteLine(f);
 

It's probably not a good idea, though, to use this in production code, as it's not really necessary (just use regular recursion) and it harms readability.