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.

Wrapping visitors with active patterns in F#

In the last post I showed how to interop F# and C# algebraic data types (ADT).

In C# you'll typically have ADTs or ADT-like structures expressed as a hierarchy of classes and the Visitor pattern to traverse/deconstruct them.

So the question is: what's the best way to use C#/VB.NET visitors in F#?

As an example, let's borrow a C# - F# comparison from Stackoverflow by Juliet Rosenthal, which models boolean operations:

public interface IExprVisitor<out T> {
    T Visit(TrueExpr expr);
    T Visit(And expr);
    T Visit(Nand expr);
    T Visit(Or expr);
    T Visit(Xor expr);
    T Visit(Not expr);
}

public abstract class Expr {
    public abstract t Accept<t>(IExprVisitor<t> visitor);
}

public abstract class UnaryOp : Expr {
    public Expr First { get; private set; }

    public UnaryOp(Expr first) {
        First = first;
    }
}

public abstract class BinExpr : Expr {
    public Expr First { get; private set; }
    public Expr Second { get; private set; }

    public BinExpr(Expr first, Expr second) {
        First = first;
        Second = second;
    }
}

public class TrueExpr : Expr {
    public override t Accept<t>(IExprVisitor<t> visitor) {
        return visitor.Visit(this);
    }
}

public class And : BinExpr {
    public And(Expr first, Expr second) : base(first, second) {}

    public override t Accept<t>(IExprVisitor<t> visitor) {
        return visitor.Visit(this);
    }
}

public class Nand : BinExpr {
    public Nand(Expr first, Expr second) : base(first, second) {}

    public override t Accept<t>(IExprVisitor<t> visitor) {
        return visitor.Visit(this);
    }
}

public class Or : BinExpr {
    public Or(Expr first, Expr second) : base(first, second) {}

    public override t Accept<t>(IExprVisitor<t> visitor) {
        return visitor.Visit(this);
    }
}

public class Xor : BinExpr {
    public Xor(Expr first, Expr second) : base(first, second) {}

    public override t Accept<t>(IExprVisitor<t> visitor) {
        return visitor.Visit(this);
    }
}

public class Not : UnaryOp {
    public Not(Expr first) : base(first) {}

    public override t Accept<t>(IExprVisitor<t> visitor) {
        return visitor.Visit(this);
    }
}

Let's say we want to write a function in F# to evaluate a boolean expression using these classes. We could use an object expression to create an inline visitor:

let rec eval (e: Expr) =
    e.Accept { new IExprVisitor<bool> with
                member x.Visit(e: TrueExpr) = true
                member x.Visit(e: And)      = eval(e.First) && eval(e.Second)
                member x.Visit(e: Nand)     = not(eval(e.First) && eval(e.Second))
                member x.Visit(e: Or)       = eval(e.First) || eval(e.Second)
                member x.Visit(e: Xor)      = eval(e.First) <> eval(e.Second)
                member x.Visit(e: Not)      = not(eval(e.First)) }

This is already more concise than the equivalent C# code, but we can do better. Once again, active patterns are the key. We only need one visitor to do the required plumbing:

module Expr = 
    open DiscUnionInteropCS

    type ExprChoice = Choice<unit, Expr * Expr, Expr * Expr, Expr * Expr, Expr * Expr, Expr>

    let private visitor = 
        { new IExprVisitor<ExprChoice> with
            member x.Visit(e: TrueExpr): ExprChoice = Choice1Of6 ()
            member x.Visit(e: And):      ExprChoice = Choice2Of6 (e.First, e.Second)
            member x.Visit(e: Nand):     ExprChoice = Choice3Of6 (e.First, e.Second)
            member x.Visit(e: Or):       ExprChoice = Choice4Of6 (e.First, e.Second)
            member x.Visit(e: Xor):      ExprChoice = Choice5Of6 (e.First, e.Second)
            member x.Visit(e: Not):      ExprChoice = Choice6Of6 e.First }

    let (|True|And|Nand|Or|Xor|Not|) (e: Expr) =
        e.Accept visitor

And now we can write eval more idiomatically and more concise:

let rec eval = 
    function
    | True          -> true
    | And(e1, e2)   -> eval(e1) && eval(e2)
    | Nand(e1, e2)  -> not(eval(e1) && eval(e2))
    | Or(e1, e2)    -> eval(e1) || eval(e2)
    | Xor(e1, e2)   -> eval(e1) <> eval(e2)
    | Not(e1)       -> not(eval(e1))

This also opens the doors for more complex pattern matching. See Juliet's post for an example.

Algebraic data type interop: F# - C#

In a previous post I wrote about encoding algebraic data types in C#. Now let's explore the interoperability issues that arise when defining and consuming algebraic data types (ADTs) cross-language in C# and F#. More concretely, let's analyze construction and deconstruction of an ADT and how to keep operations as idiomatic as possible while also retaining type safety.

Defining an ADT in F# and consuming it in C#

In F#, ADTs are called discriminated unions. The first thing I should mention is that the F# component design guidelines recommend hiding discriminated unions as part of a general .NET API. I prefer to interpret it like this: if you can hide it with minor consequences, or you have stringent binary backwards compatibility requirements, or you foresee it changing a lot, hide it. Otherwise I wouldn't worry much.

Let's use this simple discriminated union as example:

type Shape =
| Circle of float
| Rectangle of float * float

Construction in C# is pretty straightforward: F# exposes static methods NewCircle and NewRectangle:

var circle = Shape.NewCircle(23.77);
var rectangle = Shape.NewRectangle(1.5, 2.2);

No, you can't use constructors directly to instantiate Circle or Rectangle, F# compiles these constructors as internal. No big deal really.

Deconstruction, however, is a problem here. C# doesn't have pattern matching, but as I showed in the previous article you can simulate this with a Match() method like this:

static class ShapeExtensions {
    public static T Match<T>(this Shape shape, Func<double, T> circle, Func<double, double, T> rectangle) {
        if (shape is Shape.Circle) {
            var x = (Shape.Circle)shape;
            return circle(x.Item);
        }
        var y = (Shape.Rectangle)shape;
        return rectangle(y.Item1, y.Item2);
    }
}

Here we did it as an extension method in the consumer side of things (C#). The problem with this is, if we add another case to Shape (say, Triangle), this will still compile successfully without even a warning, but fail at runtime, instead of failing at compile-time as it should!

It's best to define this in F# where we can take advantage of exhaustively-checked pattern matching, either as a regular instance member of Shape or as an extension member:

[<Extension>]
type Shape with
    [<Extension>]
    static member Match(shape, circle: Func<_,_>, rectangle: Func<_,_,_>) =
        match shape with
        | Circle x -> circle.Invoke x
        | Rectangle (x,y) -> rectangle.Invoke(x,y)

This is how we do it in FSharpx to work with Option and Choice in C#.

Defining an ADT in C# and consuming it in F#

Defining an ADT in C# is already explained in my previous post. But how does this encoding behave when used in F#?

To recap, the C# code we used is:

namespace DiscUnionInteropCS {
    public abstract class Shape {
        private Shape() {}

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

            public Circle(double 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;
            }
        }

        public T Match<T>(Func<double, 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.Height, y.Width);
        }
    }
}

Just as before, let's analyze construction first. We could use constructors:

let shape = Shape.Circle 2.0

which looks like a regular F# discriminated union construction with required qualified access. There are however two problems with this:

1. Object constructors in F# are not first-class functions. Try to use function composition (>>) or piping (|>) with an object constructor. It doesn't compile. On the other hand, discriminated union constructors in F# are first-class functions.
2. Concrete case types lead to unnecessary upcasts. shape here is of type Circle, not Shape. This isn't much of a problem in C# because it upcasts automatically, but F# doesn't, and so a function that returns Shape would require an upcast.

Because of this, it's best to wrap constructors:

let inline Circle x = Shape.Circle x :> Shape
let inline Rectangle (a,b) = Shape.Rectangle(a,b) :> Shape

Let's see deconstruction now. In F# this obviously means pattern matching. We want to be able to write this:

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

We can achieve this with a simple active pattern that wraps the Match method:

let inline (|Circle|Rectangle|) (s: Shape) =
    s.Match(circle = (fun x -> Choice1Of2 x),
            rectangle = (fun x y -> Choice2Of2 (x,y)))

For convenience, put this all in a module:

module Shape =
    open DiscUnionInteropCS

    let inline Circle x = Shape.Circle x :> Shape
    let inline Rectangle (a,b) = Shape.Rectangle(a,b) :> Shape
    let inline (|Circle|Rectangle|) (s: Shape) =
        s.Match(circle = (fun x -> Choice1Of2 x),
                rectangle = (fun x y -> Choice2Of2 (x,y)))

So with a little boilerplate you can have ADTs defined in C# behaving just like in F# (modulo pretty-printing, comparison, etc, but that's up the C# implementation if needed). No need to to define a separate, isomorphic ADT.

Note that pattern matching on the concrete type of a Shape would easily break, just like when we defined the ADT in F# with Match in C#. By using the original Match, if the original definition is modified, Match() will change and so the active pattern will break accordingly at compile-time. If you need binary backwards compatibility however, it's going to be more complex than this.

In the next post I'll show an example of a common variant of this.

By the way it would be interesting to see how ADTs in Boo and Nemerle interop with F# and C#.