A non-empty list type for .NET

A simple immutable list like the fundamental list type in OCaml, F# or Haskell can be expressed as:

type 'a Alist = 
    | Nil 
    | Cons of 'a * 'a Alist 

That is, it's either empty, or it's non-empty. We could refactor the non-empty part to a record type:

type 'a Alist = 
    | Nil 
    | Cons of 'a NonEmptyList 
and 'a NonEmptyList = { Head: 'a; Tail: 'a Alist }

This NonEmptyList type is clearly not a new data structure (it's still an immutable list). It may seem silly at first to use this as a separate list type, but it actually goes a long way towards making illegal states unrepresentable.

Because it is guaranteed not to be empty by the type system, it has certain interesting properties. For one, obviously getting the head of a non-empty list will always work, for any instance of the type, while List.head throws an exception for an empty list (here's the proof of why it can't have any other behavior).

The F# List module has many such partial functions that are undefined for empty lists: head, tail, reduce, average, min, max... and of course the respective functions in the Seq module and System.Linq.Enumerable. If you want to use one of these functions on a regular list/IEnumerable, you either have to immediately check if the input is empty first, and return a 'default' value (many people wrap this in a function e.g. MaxOrDefault(defaultValue), effectively making it a total function); or catch the possible exception every time. Otherwise you're risking a possible failure. Another way to make these functions total is by simply removing the empty list from the domain, that is, operating on non-empty lists.

The Haskell community generally recommends avoiding such trivially avoidable partial functions [1] [2] [3], and this advice applies equally to most (all?) languages, especially typed languages. At the very least, it's useful to be aware of where and why you're using a partial function.

Applicative validation makes for a good example of NonEmptyLists. I've written about applicative functor validation before, in F# and in C#, with examples. The type I used to represent a validation was Choice<'a, string list>. This means: either the value (when it's correct), or a list of errors. But strictly speaking, this type is too "loose", since it allows the value Choice2Of2 [], which intuitively means "The input was invalid, but there is no error". This simply doesn't make any sense. If the input is invalid, there must be at least one error. Thus, the correct type to use here is Choice<'a, string NonEmptyList>.

Another occurrence of NonEmptyList recently popped up while I was writing a library to bind the Urchin Data API. In this API there's a parameter that is mandatory, but admits more than one value: a perfect match for a NonEmptyList.

In general, when you find yourself not knowing what to do with the empty list case, or when you think "this list can't possibly be empty here", it may be an indication that you need a NonEmptyList.

The code is currently in my fork of FSharpx, it includes the usual functions: cons, map, append, toList, rev, collect, etc.

It's also usable from C#, here are some tests showing this.

I briefly touched on the subject of totality here, which has deep connections to Turing completeness. Here's some recommended further reading about it:

• "On the importance of purity" by Sandro Magi, in particular the section "The benefits of totality" is a great introduction.
• "Total functional programming" by D. A. Turner
• "Getting to the bottom of nothing at all" by James Iry, an introduction to bottom, its connection to Turing-completeness, laziness and exceptions.
• "Bottom and partial functions", a formal treatment in the context of denotational semantics.

Optional parameters interop: C# - F#

Both C# and F# support optional parameters. But since they're implemented differently, how well do they play together? How well do they interop?

Here's I'll analize both scenarios: consuming F# optional parameters from C#, and consuming C# optional parameters from F#.

For reference, I'm using VS2012 RC (F# 3.0, C# 5.0)

Calling C# optional parameters in F#

Let's start with some C# code that has optional parameters and see how it behaves in F#:

public class CSharp {
    public static string Something(string a, int b = 1, double c = 2.0) {
        return string.Format("{0}: {1} {2}", a, b, c);
    }
}

Here are some example uses of this function:

var a = CSharp.Something("hello");
var b = CSharp.Something("hello", 2);
var c = CSharp.Something("hello", 2, 3.4);

Now we try to call this method from F# and we see:

Uh-oh, those parameters sure don't look very optional. However, it all works fine and we can write:

let a = CSharp.Something("hello")
let b = CSharp.Something("hello", 2)
let c = CSharp.Something("hello", 2, 3.4)

which compiles and works as expected.

Calling F# optional parameters in C#

Now the other way around, a method defined in F#, using the F# flavor of optional parameters:

type FSharp = 
    static member Something(a, ?b, ?c) = 
        let b = defaultArg b 0 
        let c = defaultArg c 0.0 
        sprintf "%s: %d %f" a b c 

We can happily use it like this in F#:

let a = FSharp.Something("hello")
let b = FSharp.Something("hello", 2)
let c = FSharp.Something("hello", 2, 3.4)

But here's how this method looks like in C#:

Yeah, there's nothing optional about those parameters.

What we need to do is to implement the C# flavor of optional parameters "manually". Fortunately that's pretty easy, just mark those parameters with the Optional and DefaultParameterValue attributes:

open System.Runtime.InteropServices

type FSharp = 
    static member Something(a, [<Optional;DefaultParameterValue(null)>] ?b, [<Optional;DefaultParameterValue(null)>] ?c) = 
        let b = defaultArg b 0 
        let c = defaultArg c 0.0 
        sprintf "%s: %d %f" a b c 

Why "null" you ask? The default value should have been None, but that's not a compile-time constant so it can't be used as an attribute argument. Null is interpreted as None.

These attributes don't affect F# callers, but now in C# we can write:

Console.WriteLine(FSharp.Something("hello"));
Console.WriteLine(FSharp.Something("hello", FSharpOption<int>.Some(5)));

So we have optional parameters but we still have to deal with option types when we want to use them. If you find that annoying or ugly, you could use FSharpx, in which case FSharpOption<int>.Some(5) turns into 5.Some() .

The astute reader will suggest an overload just to handle the C# compatibility case. Alas, that doesn't work in the general case. Let's try and see what happens:

type FSharp = 
    static member private theActualFunction (a, b, c) =
        sprintf "%s: %d %f" a b c

    static member Something(a, ?b, ?c) =
        let b = defaultArg b 0
        let c = defaultArg c 0.0
        FSharp.theActualFunction(a,b,c)

    static member Something(a, [<Optional;DefaultParameterValue(0)>] b, [<Optional;DefaultParameterValue(0.0)>] c) =
        FSharp.theActualFunction(a,b,c)

Note that I moved the "actual working function" to a separate method, otherwise the second overload would just recurse. But we have a duplication in the definition of the default values. Still, the real problem shows when we try to use this in F#:

let d = FSharp.Something("hello", 2, 3.4)

This doesn't compile as F# can't figure out which one of the overloads to use.

Conclusion

F# has no issues consuming optional parameters defined in C#.

When writing methods with optional parameters in F# to be called from C#, either add the corresponding attributes and deal with the option types, or add a separate non-overloaded method. Or forget the optional parameters altogether and add overloads, just as we all did in C# before it supported optional parameters.

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 F# DSL for MbUnit

In F# we typically organize tests much like in C# or VB.NET: writing functions marked with a [<Test>] attribute or similar. Actually there's a slight advantage in F#: you don't need to write a class marked as test fixture, you can directly write the tests as let-bound functions. Still, it's fundamentally the same model. (If you're into BDD there's also TickSpec as an alternative model).

Since it's the same model, you get the same issues I described in my last post, and then some: for example as Kurt explains, attributes in F# sometimes aren't treated exactly as in C#.

Also in my last post, I wrote about how MbUnit supports first-class tests as an alternative to attribute-defined tests. In F# we can take advantage of this and custom operators to build a very concise DSL to define tests.

First let's see a small test suite with setup/teardown, written with the classic attributes:

[<TestFixture>]
type ``MemoryStream tests``() =
    let mutable ms : MemoryStream = null

    [<SetUp>]
    member x.Setup() =
        ms <- new MemoryStream()

    [<TearDown>]
    member x.Teardown() =
        ms.Dispose()

    [<Test>]
    member x.``Can read``() =
        Assert.IsTrue ms.CanRead

    [<Test>]
    member x.``Can write``() =
        Assert.IsTrue ms.CanWrite

Looks simple enough, right? And yet, the mutable field is a smell, or at least an indicator that this isn't functional. Let's try to get rid of that mutable.

As a first step we'll rewrite this as first-class tests, that is, using [<StaticTestFactory>] as shown in my last post:

[<StaticTestFactory>]
let testFactory() =
    let suite = TestSuite("MemoryStream tests")
    let ms : MemoryStream ref = ref null
    suite.SetUp <- fun () -> ms := new MemoryStream()
    suite.TearDown <- fun () -> (!ms).Dispose()
    let tests = [
        TestCase("Can read", 
            fun () -> Assert.IsTrue (!ms).CanRead)
        TestCase("Can write", 
            fun () -> Assert.IsTrue (!ms).CanWrite)
    ]
    Seq.iter suite.Children.Add tests
    [suite]

Oh great, that's even uglier than what we started with! And we have replaced the mutable field with a ref cell, not much of an improvement. 
But bear with me, we have first-class tests now so there's a lot a room for improvement.

In order to keep refactoring this, we need to realize that the problem is that our test cases should be functions MemoryStream -> unit instead of unit -> unit. That way, they wouldn't have to depend on an external MemoryStream instance; instead the instance would be pushed somehow to the test. Let's write that:

let tests = [
    "Can read", (fun (ms: MemoryStream) -> Assert.IsTrue ms.CanRead)
    "Can write", (fun ms -> Assert.IsTrue ms.CanWrite)
]

Now we have this list of strings and MemoryStream -> unit functions. What we need now is to turn these functions into unit -> unit so we can ultimately build TestCases.

In other words, we need a function (MemoryStream -> unit) -> (unit -> unit). This function should create the MemoryStream, pass it to our test function, then dispose the MemoryStream. Hey, what do you know, turns out that's just what SetUp and TearDown do!

Still with me? It's much easier to see this in code:

let withMemoryStream f () = 
    use ms = new MemoryStream()
    f ms

Now we apply this to our list, building the TestCases and then the TestSuite:

[<StaticTestFactory>]
let testFactory() =
    let suite = TestSuite("MemoryStream tests")
    tests 
    |> Seq.map (fun (n,t) -> TestCase(n, Gallio.Common.Action(withMemoryStream t)))
    |> Seq.iter suite.Children.Add
    [suite]

We've eliminated all mutable references, and also replaced SetUp/TearDown with a simple higher-order function.

But we can do still better, in terms of readability. We can define a few custom operators to hide the TestSuite and TestCase constructors:

let inline (=>>) name tests =
    let suite = TestSuite(name)
    Seq.iter suite.Children.Add tests
    suite :> Test

let inline (=>) name (test: unit -> unit) =
    TestCase(name, Gallio.Common.Action test) :> Test

[<StaticTestFactory>]
let testFactory() =
    [
        "MemoryStream tests" =>> [
            "Can read" => 
                withMemoryStream(fun ms -> Assert.IsTrue ms.CanRead)
            "Can write" => 
                withMemoryStream(fun ms -> Assert.IsTrue ms.CanWrite)
        ]
    ]

And with a couple more operators we get rid of the duplicate call to withMemoryStream:

let inline (+>) f =
     Seq.map (fun (name, partialTest) ->
                    name => f partialTest)

let inline (==>) (name: string) test = name,test

[<StaticTestFactory>]
let testFactory() =
    [
        "MemoryStream tests" =>>
            withMemoryStream +> [
                "Can read" ==> 
                    fun ms -> Assert.IsTrue ms.CanRead
                "Can write" ==>
                    fun ms -> Assert.IsTrue ms.CanWrite
            ]
    ]

Conclusions

Confused about all those kinds of arrows? The good thing about first-class tests is that you can build them any way you want, no need to use these operators if you don't like them. That's also precisely one of its downsides: as there is no fixed idiom, it can get harder to read compared to attribute-based test definitions, where there is a single, well-defined way to do things.

In my last post I showed how first-class tests practically eliminate the concept of parameterized tests. In this post I showed how they eliminate the concept of setup/teardown, replacing them with a higher-order function, a more generic concept.

More generally, I'd say that whatever domain you're modeling (in this case, tests), there is much to gain if the core concepts are representable as first-class values. It should also be noted that different languages have very different notions of what language objects are first-class values. Some are more flexible than others, but that doesn't imply any superiority by itself. However it does mean that if you're not aware of this you'll probably misuse your language and end up with ever more complex workarounds to manipulate your domain objects as values. Nice APIs, conventions, configuration, etc, are all secondary and can be built much more easily on top of composable, first-class building blocks.

But I digress. In the next post I'll show a simple testing library built around tests as first-class values and more pros/cons about this approach.