Monday, August 29, 2011

Validating with applicative functors in F#

In my last post I showed how to validate using applicative functors in C#. LINQ helps a lot with making the syntax bearable.

In F# we have other tools to encode applicative functors: custom operators and type inference. And thanks to pattern matching it's much easier to define the validation applicative functor operations in F# (but I won't show that here).

So let's see what the C# code from the last post looks like in F#. Hopefully this article will serve both C# developers interested in learning F# and F# developers interested in learning more about applicative functors. F# programmers will probably find the first part boring and might want to go directly to the second part.

Defining the primitives

Starting from the bottom up, here's the function that builds a validator from a predicate:

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

Same thing in F#:

let validator pred error x =
    if pred x
        then Choice1Of2 x
        else Choice2Of2 [error]

We don't need the Ok and Error constructors because F# correctly infers the appropriate types. In fact, we did not use a single type annotation!

We don't need to explicitly state that we're returning a function, as we'll see now:

static FSharpChoice<T, Errors> NonNull<T>(T value, string err) where T: class {
    return Validator<T>(x => x != null, err)(value);

Same in F# :

let (==) = LanguagePrimitives.PhysicalEquality
let inline (!=) a b = not (a == b)

let nonNull e = validator ((!=) null) e

Readers unfamiliar with F# might wonder about the definition of == and !=. The answer is: F# doesn't have a built-in reference equality operator, and with good reason: usually you want to compare things by their structure rather than by reference. We could have used F# structural equality here (the <> operator in this case) but this would have placed an additional equality type restriction. It doesn't really matter in this case but we'll try to keep things as close as possible to the equivalent C# code. If you want to learn more about structural equality I refer you to this very thorough article by Brian McNamara.

C# programmers that are still paying any attention to this code (gotcha! ;-) should have noticed that I defined the validator function with three parameters (pred, error, x), yet I only defined the first two arguments when defining nonNull. Where did the other parameter go? This is an example of partial application of a curried function. Currying and partial application are often confused with each other, but they're not the same thing. Ivan Towlson has a great series of articles about partial application in F# and comparing it to C#. I also recomend this article (and related) by Dustin Campbell.

Moving on:

static FSharpChoice<T, Errors> NotEqual<T>(T value, T other, string err) {
    return Validator<T>(v => !Equals(v, other), err)(value);

Same in F# :

let notEqual a = validator ((<>) a)

Here we did use structural equality, we certainly don't want to compare things by reference. Object.Equals is not the same as F#'s structural equality. Something probably a little closer would be requiring T to implement IEquatable<T> in the C# function, but still not the same.

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

Same in F# :

let validateAddressLines =
        (fun (a: Address) -> a.Line1 != null || a.Line2 == null) 
        "Line1 is empty but Line2 is not"

Nothing interesting here. Next:

static FSharpChoice<T?, Errors> GreaterThan<T>(T? value, T? other, string err) where T: struct, IComparable<T> {
    if (!value.HasValue && !other.HasValue || value.HasValue != other.HasValue || value.Value.CompareTo(other.Value) > 0)
        return FSharpChoice.Ok(value);
    return FSharpChoice.Error<T?>(err);

The bad news here is that F# doesn't have built-in support for nullable types. Fortunately, it's not too hard to write a few functions and get decent syntax. I already did that about a year ago so I'll just use it here:

let greaterThan o = validator ((<?) o)

No, that's not a typo: due to the way operators are defined, they have to be read backwards when partially applied. You can be a bit more explicit/verbose and instead say:

let greaterThan o = validator (fun a -> a >? o)

Combining functions through monads and applicative functors

Now that we have all primitives defined, let's get to the interesting part: combine them with an applicative functor and monad.

I've blogged about applicative functors in F# many times... very briefly, there are two operations: pure (puree in F#) and apply (<*> in F#). And we define this convenience function (this is standard for applicative functors):

let inline (<!>) f x = puree f <*> x

Here's ValidateAddress() in C# using LINQ to encode the applicative functor:

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;

Here's the equivalent in F# :

let validateAddress (a: Address) = 
    fun x y -> a
    <!> nonNull "Post code can't be null" a.Postcode
    <*> validateAddressLines a

If you squint a little, they're not that different really. We can go a bit further to avoid having those dummy values x and y that we end up ignoring anyway. We only need to define (these are also standard functions):

let inline lift2 f a b = f <!> a <*> b
let inline ( <*) a b = lift2 (fun z _ -> z) a b

Now we can say:

let validateAddress (a: Address) = 
    puree a
    <* nonNull "Post code can't be null" a.Postcode
    <* validateAddressLines a

Validating a single Order in C#:

static FSharpChoice<Order, Errors> ValidateOrder(Order o) {
        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}' must be positive", name))
        select o;

Unlike the previous validators, this one is monadic, not applicative. In F# we have some alternatives. We can use a computation expression:

let validateOrder (o: Order) =
    validation {
        let! name = nonNull "Product name can't be null" o.ProductName
        let! _ = greaterThan (0m).n (sprintf "Cost for product '%s' must be positive" name) o.Cost
        return o

Or we can use monadic operators directly:

let validateOrder (o: Order) =
    let nameNotNull = nonNull "Product name can't be null" o.ProductName
    let positiveCost n = greaterThan (0m).n (sprintf "Cost for product '%s' can't be negative" n) o.Cost
    nameNotNull >>= positiveCost |> map (fun _ -> o)

The higher-order function to make this operate on sequences of orders:

static FSharpChoice<FSharpList<Order>, Errors> ValidateOrders(IEnumerable<Order> orders) {
    var zero = ListModule.Empty<Order>().PureValidate();
    return orders
        .Aggregate(zero, (e, c) => from a in e
                                   join b in c on 1 equals 1
                                   select a.Cons(b));

Same in F# :

let inline flip f a b = f b a
let inline cons a b = a::b
let seqValidator f = 
    let zero = puree [] f >> Seq.fold (lift2 (flip cons)) zero
let validateOrders c = seqValidator validateOrder c

And the final validations with an sample application:

let customer = 
        Surname = "foo",
        Address = Address(Postcode = "1424"),
        Orders = ResizeArray([
                                Order(ProductName = "Foo", Cost = (5m).n)
                                Order(ProductName = "Bar", Cost = (-1m).n)
                                Order(ProductName = null , Cost = (-1m).n)
let result = 
    puree customer
    <* nonNull "Surname can't be null" customer.Surname
    <* notEqual "foo" "Surname can't be foo" customer.Surname
    <* validateAddress customer.Address
    <* validateOrders customer.Orders
match result with
| Choice1Of2 c -> printfn "Valid customer: %A" c
| Choice2Of2 errors -> printfn "Invalid customer. Errors:\n%A" errors

Wrap it up already!

I know, I know, this post is too long already. Hopefully this step-by-step, side-by-side comparison will help C# programmers see some of the power of F# through currying, partial application, custom operators and type inference, in a non-trivial example. And F# developers can see another use for applicative functors: validation.

Code is here.


Dax said...

Is there any advantage to using the applicative syntax versus using the monadic syntax? The monadic allows you to define intermediate values and appears more flexible that way.

Mauricio Scheffer said...

@Dax : Applicative accumulates errors. Monadic replaces errors.

Laygr said...

I don't see any ValidationBuilder on FSharpx, but I see you used it "validation {..."
How would you define it?

Mauricio Scheffer said...

@Laygr use FSharpx.Choice.choose { ... } instead.