Programming with algebraic effects and handlers, a method for reasoning about computational effects of programs that originates from functional programming research, has recently found increasing adoption in more mainstream languages. Implementations can be found in OCaml, Haskell, Scala, F# and the Koka language.

Algebraic effects are an immensely powerful language feature that can be used to implement a diverse array of features such as dependency injection, cancellation, nondeterminism, debug tracing, first-class continuations and replayable computations.

For a beginner’s introduction to the concept of algebraic effects, I would recommend reading Dan Abramov’s excellent article on the subject, which provides a primer using a hypothetical dialect of JavaScript.

In this article I will be talking about Eff, an experimental C# library that provides a pragmatic adaptation of the concept by taking advantage of the async method extensibility features available since C# 7. It was originally created by my former colleague, Nick Palladinos, and recently I have also been contributing to the project.

I have decided to start writing about Eff since I strongly believe in its experimental potential, and since hardly any documentation exists about it online.

Key Concepts

At its core, the library defines a task-like type, Eff, which can be built using async methods:

using Nessos.Effects;

async Eff<int> Sqr(int x) => x * x;

and can be composed using the await keyword:

async Eff<int> SumOfSquares(params int[] inputs)
{
    int sum = 0;
    foreach (int input in inputs)
    {
        sum += await Sqr(input);
    }
    return sum;
}

An Eff computation has to be run explicitly by passing an effect handler:

using Nessos.Effects.Handlers;

Eff<int> computation = SumOfSquares(1,2,3);

computation.Run(new DefaultEffectHandler());

It should be noted that unlike Task, Eff values have delayed semantics and so running

async Eff HelloWorld() => Console.WriteLine("Hello, World!");

Eff hello = HelloWord();

will have no observable side-effect. It is useful to think of Eff values as delegates, as opposed to futures.

Finally, Eff methods are capable of awaiting regular async awaitables

async Eff Delay()
{
    await Task.Delay(1000);
}

It should be noted however that the opposite is not possible, that is Eff values cannot be awaited inside regular async methods.

Programming with Effects

The examples thus far illustrate what is effectively an alternative implementation for async method builders. We have not talked about effects yet.

In the Eff library, abstract effects can be defined by inheriting the abstract Effect<T> class:

public class DateTimeNowEffect : Effect<DateTime>
{

}

Abstract effects can be awaited inside Eff computations:

async Eff<bool> IsSummerWeekend()
{
    DateTime now = await new DateTimeNowEffect();
    return (now.Month, now.DayOfWeek) switch
    {
        (6 or 7 or 8, DayOfWeek.Saturday or DayOfWeek.Sunday) => true,
        _ => false,
    };
}

And Eff computations depending on Effects can be further composed with other Eff computations:

async Eff SomeDomainLogic(Customer customer)
{
   if (await IsSummerWeekend())
   {
       await SendIceCreamPromo(customer);
   }
}

Let’s now see how we can run this effect computation. Suppose I try to pass it the default effect handler:

SomeDomainLogic(customer).Run(new DefaultEffectHandler());

Then execution will fail with an exception:

System.NotSupportedException: Abstract effects not supported by this handler.
   at Nessos.Effects.Handlers.DefaultEffectHandler.Handle[TResult](EffectAwaiter`1 awaiter) 

The failure is caused by the fact that the effect handler we used does not provide semantics for DateTimeNowEffect. In order to get this to work we need to implement an effect handler of our own:

public class DateTimeEffectHandler : EffectHandler
{
    public override async ValueTask Handle<TResult>(EffectAwaiter<TResult> awaiter)
    {
        switch (awaiter)
        {
            case EffectAwaiter<DateTime> { Effect: DateTimeNowEffect } dateTimeEffectAwaiter:
                dateTimeEffectAwaiter.SetResult(DateTime.Now);
                break;
        }
    }
}

The handler runs a pattern match over an EffectAwaiter argument, and populates any DateTimeNowEffect awaiter with the result of System.DateTime.Now. We can now run the previous computation with our new effect handler:

SomeDomainLogic(customer).Run(new DateTimeEffectHandler());

which will execute with the expected result.

We can also use effect handlers to mock the result of an effect:

public class MockedDateTimeEffectHandler : EffectHandler
{
    public DateTime Now { get; set; }

    public override async ValueTask Handle<TResult>(EffectAwaiter<TResult> awaiter)
    {
        switch (awaiter)
        {
            case EffectAwaiter<DateTime> { Effect: DateTimeNowEffect } dateTimeEffectAwaiter:
                dateTimeEffectAwaiter.SetResult(Now);
                break;
        }
    }
}

var handler = new MockedDateTimeEffectHandler() { Now = DateTime.Parse("2020-07-19") };
SomeDomainLogic(customer).Run(handler);

Combining Effects

Consider the following set of abstract console effects

public static class ConsoleEffect
{
    public static WriteLineEffect WriteLine(string line) => new WriteLineEffect() { LogEntry = line };
    public static ReadLineEffect ReadLine() => new ReadLineEffect();

    public class WriteLineEffect : Effect
    {
        public string? LogEntry { get; set; }
    }

    public class ReadLineEffect : Effect<string>
    {

    }
}

and relevant handler that is backed by System.Console:

public class ConsoleEffectHandler : EffectHandler
{
    public override async ValueTask Handle<TResult>(EffectAwaiter<TResult> awaiter)
    {
        switch (awaiter)
        {
            case EffectAwaiter { Effect: ConsoleEffect.WriteLineEffect writeLineEffect } writeLineAwaiter:
                Console.WriteLine(writeLineEffect.LogEntry);
                writeLineAwaiter.SetResult();
                break;

            case EffectAwaiter<string> { Effect: ConsoleEffect.ReadLineEffect } readLineAwaiter:
                string line = Console.ReadLine();
                readLineAwaiter.SetResult(line);
                break;
        }
    }
}

Now suppose we have an Eff computation that combines effects from both examples:

async Eff Test()
{
    DateTime now = await new DateTimeNowEffect();
    await ConsoleEffect.WriteLine($"The current date is {now}.");
}

Then defining an effect handler that supports both effect families is very straightforward:

public class CombinedDateTimeConsoleEffectHandler : EffectHandler
{
    private readonly EffectHandler[] _nestedHandlers = new EffectHandler[]
    {
        new ConsoleEffectHandler(),
        new DateTimeEffectHandler(),
    };

    public override async ValueTask Handle<TResult>(EffectAwaiter<TResult> awaiter)
    {
        foreach (EffectHandler handler in _nestedHandlers)
        {
            await handler.Handle(awaiter);
            if (awaiter.IsCompleted)
            {
                return;
            }
        }
    }
}

Test().Run(new CombinedDateTimeConsoleEffectHandler());

It should be then clear by the examples that effects can be used to define a form of dependency injection. There is however a twist: since effect handlers flow with function calls, there is no need to pass dependencies via constructor parameters. Domain logic can be expressed by composing static methods, with the effect handler serving as the composition root for the application. This provides a truly functional approach to dependency injection.

Encoding Cancellation

A common criticism of C# is that async methods do not flow cancellation, that is any cancellation tokens will have to be passed manually to operations that require it. We will now see how one might use effects to work around that limitation; the Eff library comes with a baked-in effect handler that provides cancellation semantics. Consider the following example:

using Nessos.Effects.Cancellation;

async Eff Test()
{
    while (true)
    {
        await Delay();

        async Eff Delay()
        {
            await Task.Delay(1000);
        }
    }
}

var cts = new CancellationTokenSource(millisecondsDelay:10_000);
var handler = new CancellationEffectHandler(cts.Token);
Test().Run(handler);

While one might expect the above to diverge, it will actually throw an OperationCanceledException after ten seconds. This is because the effect handler will actively check for cancellation before evaluating the state machine of a nested Eff call.

But what happens if we need to pass the cancellation token to a non-eff asynchronous operation? We can recover it by awaiting on the cancellation token effect:

async Eff<HttpResponseMessage> Get(HttpClient httpClient, string requestUri)
{
    // get the cancellation token from the effect handler
    CancellationToken token = await CancellationTokenEffect.Value;
    return await httpClient.GetAsync(requestUri, token);
}

For those familiar with F#, this is precisely how its async method implementation flows cancellation.

Conclusions

This concludes my introductory overview of the Eff library. I have tried to convey its most basic concepts, however this article hardly covers all capabilities of effects. I will try to follow up with future articles digging deeper into both applications and the implementation details of Eff itself. For the impatient, there is a fairly extensive catalog of samples in the Eff repo itself, including a proof-of-concept AspNetCore application.

I do hope that you have found the concepts interesting, and that this might furthermore spark a conversation about future programming paradigms.

A few years back, I blogged about how one could use the TypeShape library for writing practical generic programs in F#. While the library has seen success in both OSS and proprietary applications, from the beginning there have existed pretty self-evident usability issues when working with the library itself.

On simple inspection of a basic example one can easily detect the following problems:

• Accessing generic types requires extensive use of visitors which result in awkward looking code, which is hard to read and hard to write.
• The type checker can hardly handle such expressions, and explicit type annotations are required almost everywhere.
• Most importantly, unsafe casts are required at the boundaries of generic program composition. While those generally only result in errors at program generation time and not at execution time, they are still a source of runtime errors.

In this article, I propose an alternative approach to generic programming in F#, one that provides a simpler and type-safe approach to building polytypic programs. The approach combines techniques that are long established in the literature.

Encoding Higher-Kinded Types

A core ingredient for the new approach is the ability to express higher-kinded types. While F# does not natively support higher-kinded types, they can be encoded using an approach first described by Yallop and White in the context of OCaml. Various ports of that encoding exist in F#, most prominent being the Higher library.

For the purposes of this application, I’m going to use a simplistic variant of the encoding:

type App<'F, 't> = App of payload : obj

module HKT =

    // associate HKT encoding to underlying type using SRTPs
    let inline private assoc<'F, 'a, 'Fa when 'F : (static member Assign : App<'F, 'a> * 'Fa -> unit)> = ()

    // pack and unpack functions
    let inline pack (value : 'Fa) : App<'F, 'a> = assoc<'F, 'a, 'Fa> ; App value
    let inline unpack (App value : App<'F, 'a>) : 'Fa = assoc<'F, 'a, 'Fa> ; unbox value
        
    // helper active pattern
    let inline (|Unpack|) app = unpack app

Let’s put the above definitions into use. Here’s how we can encode optionals as a higher-kinded type:

type Option =
    static member Assign(_ : App<Option, 'a>, _ : 'a option) = ()

let encoded : App<Option, _> = HKT.pack (Some 42)
let payload = HKT.unpack encoded

The HKT.pack function takes an instance of type int option and returns an instance of type App<Option, int>, whereas unpack does the inverse. The type Option is an uninhabited type representing the _ option type constructor and is known as the brand of the encoding. The compiler infers the association between App<Option, int> and int option by virtue of the Assign method type signature using SRTP method constraints.

Let’s see how we can use this encoding to express programs that are generic w.r.t. type constructors. Here’s the obligatory functor example:

type Functor<'F> =
    abstract member Fmap : ('a -> 'b) -> App<'F, 'a> -> App<'F, 'b>

let fmap f xs : _ when 'F :> Functor<'F> = (new 'F()).Fmap f xs

let incrSqr x = x |> fmap ((+) 1) |> fmap ((*) 2)

Here we describe the functor abstraction using an interface that is generic w.r.t the higher-kinded brand. We also use default constructor constraints and type inference to define a generic fmap combinator and a sample pipeline on top of that.

We can create functor instances as follows:

[<Struct>]
type List =
    static member Assign(_ : App<List, 'a>, _ : 'a list) = ()
    interface Functor<List> with
        member __.Fmap f (HKT.Unpack xs) = HKT.pack (List.map f xs)

let lst : App<List,_> = HKT.pack [1;2;3;4]

incrSqr lst |> HKT.unpack
// val it : int list = [4; 6; 8; 10]

If you’re interested in more elaborate HKT encodings, please refer to the original paper or the samples in the Higher library.

Application to Generic Programming

A very common generic programming application is the pretty printer. It involves taking an arbitrary type 'a and generating a function of type 'a -> string. It can be represented using a higher-kinded type encoding like so:

type PrettyPrinter =
    static member Assign(_ : App<PrettyPrinter, 'a>, _ : 'a -> string) = ()

Thus, generating a pretty-printer for type 'a boils down to obtaining an instance of type App<PrettyPrinter,'a>.

Defining Higher-Kinded Generic Programs

We can combine the ideas described above to obtain an abstraction capable of describing most generic programming applications. Consider the interface:

type ITypeBuilder<'F> =
    // base types
    abstract Bool : unit -> App<'F, bool>
    abstract Int : unit -> App<'F, int>
    abstract String : unit -> App<'F, string>
    // combinators
    abstract Option : App<'F, 't> -> App<'F, 't option>
    abstract List : App<'F, 't> -> App<'F, 't list>
    abstract Tuple : App<'F, 't1> -> App<'F, 't2> -> App<'F, 't1 * 't2>

Which defines a set of constructors capable of producing generic programs for a small subset of types. As before, we can use a bit of type inference to expose the interface methods as proper combinators:

let inline private inst() : 'F when 'F :> ITypeBuilder<'F> = new 'F()
let bool () = inst().Bool()
let int () = inst().Int()
let string () = inst().String()
let option t = inst().Option t
let list t = inst().List t
let tuple t = inst().Tuple t

Then, writing

let sample () = int () |> list |> option |> tuple (bool ())

Produces a generic constructor for instances of type App<'F,bool * int list option>.

We can now produce a generic pretty-printer by implementing the ITypeBuilder interface:

[<Struct>]
type PrettyPrinter =
    static member Assign(_ : App<PrettyPrinter, 'a>, _ : 'a -> string) = ()

    interface ITypeBuilder<PrettyPrinter> with
        member __.Bool () = HKT.pack (function true -> "true" | false -> "false")
        member __.Int () = HKT.pack (fun i -> i.ToString())
        member __.String() = HKT.pack (sprintf "\"%s\"")

        member __.Option (HKT.Unpack ep) = HKT.pack(function None -> "None" | Some x -> sprintf "Some(%s)" (ep x))
        member __.List (HKT.Unpack ep) = HKT.pack(Seq.map ep >> String.concat "; " >> sprintf "[%s]")
        member __.Tuple (HKT.Unpack lp) (HKT.Unpack rp) = HKT.pack (fun (l,r) -> sprintf "(%s, %s)" (lp l) (rp r))

Which we can consume as follows:

let mkPrinter (x : App<PrettyPrinter,_>) = HKT.unpack x

let p = sample() |> mkPrinter

p (false, Some [1;2])
// val it : string = "(false, Some([1; 2]))"

The same sample value can be reused in the context of other generic programs. Here is one that returns values with zeroed out fields:

[<Struct>]
type Zero =
    static member Assign(_ : App<Zero, 'a>, _ : 'a) = ()

    interface ITypeBuilder<Zero> with
        member __.Bool () = HKT.pack false
        member __.Int () = HKT.pack 0
        member __.String() = HKT.pack ""

        member __.Option (HKT.Unpack z) = HKT.pack(Some z)
        member __.List (HKT.Unpack z) = HKT.pack [z]
        member __.Tuple (HKT.Unpack lz) (HKT.Unpack rz) = HKT.pack (lz,rz)


let mkZero (x : App<Zero,_>) = HKT.unpack x

sample() |> mkZero
// val it : bool * int list option = (false, Some [0])

For the sake of completeness, I should mention that this application is a special case of the tagless-final pattern, which was originally described in a paper by Kiselyov et al.

Folding arbitrary types

One issue with the above approach is that we need to explicitly construct the App<_,_> instances by calling the combinators. While this might be acceptable in the context of simple applications, we’d still like a way to generate programs just by passing a simple type argument.

Luckily, this can be achieved by harnessing the usual TypeShape constructs:

let rec fold<'F, 't when 'F :> ITypeBuilder<'F> and 'F : (new : unit -> 'F)> () : App<'F, 't> =
    let wrap (x : App<'F,_>) : App<'F, 't> = unbox x
    match shapeof<'t> with
    | Shape.Bool -> bool() |> wrap
    | Shape.Int32 -> int() |> wrap
    | Shape.String -> string() |> wrap
    | Shape.FSharpOption s ->
        s.Element.Accept {
            new ITypeVisitor<App<'F, 't>> with
                member __.Visit<'e> () =
                    let e = fold<'F, 'e>()
                    option e |> wrap
        }

    | Shape.FSharpList s ->
        s.Element.Accept {
            new ITypeVisitor<App<'F, 't>> with
                member __.Visit<'e> () =
                    let e = fold<'F, 'e>()
                    list e |> wrap
        }

    | Shape.Tuple s when s.Elements.Length = 2 ->
        let ls = s.Elements.[0].Member
        let rs = s.Elements.[1].Member
        ls.Accept {
            new ITypeVisitor<App<'F, 't>> with
                member __.Visit<'l> () =
                    rs.Accept {
                        new ITypeVisitor<App<'F, 't>> with
                            member __.Visit<'r>() =
                                let l = fold<'F, 'l>()
                                let r = fold<'F, 'r>()
                                tuple l r |> wrap
                    }
        }
    | _ -> failwithf "I do not know how to fold type %O" typeof<'t>

It is then possible to define a generic pretty-printer by doing the following:

let mkPrettyPrinter<'a> () = fold<PrettyPrinter, 'a> () |> HKT.unpack

let p' = mkPrettyPrinter<int * (bool list * string option)> ()

p' (42, ([false;true], Some "string"))
// val it : string = "(42, ([false; true], Some("string")))"

As before, we can reuse the fold function for the zero program:

let zero<'a> = fold<Zero, 'a> () |> HKT.unpack

zero<int * (string option * bool list)>  
// val it : int * (string option * bool list) = (0, (Some "", [false]))

You can find the code sample above in fssnip, complete with type annotations.

Conclusions

While the ideas above are in an early prototype state, the approach in general seems very promising. It significantly simplifies the generic program authoring process by being type safe, eliminating visitors and requiring almost no type annotations. While it may lack the flexibility of the TypeShape constructs, it seems to be good enough for most generic programming applications.

You can find more involved implementations of the above idea in the TypeShape samples folder.

At Jet we do a lot of event sourcing. Our event types are typically modelled using discriminated unions:

type CartEvent =
    | CartCreated
    | ItemAdded of ItemAdded
    | ItemRemoved of ItemRemoved
    | CartCheckedOut of CartCheckedOut

and ItemAdded = { skuId : string ; quantity : int }
and ItemRemoved = { skuId : string }
and CartCheckedOut = { paymentDetails : string }

Since DUs carry no canonical representation in most popular serialization formats, encoding and decoding typically involves a bit of manual work:

let encode = function
    | CartCreated -> "cartCreated", "null"
    | ItemAdded e -> "itemAdded", serialize e
    | ItemRemoved e -> "itemRemoved", serialize e
    | CartCheckedOut e -> "cartCheckedOut", serialize e

let decode = function
    | "cartCreated", _ -> CartCreated
    | "itemAdded", json -> ItemAdded(deserialize json)
    | "itemRemoved", json -> ItemAdded(deserialize json)
    | "cartCheckedout", json -> CartCheckedOut(deserialize json)
    | t,_ -> failwithf "unrecognized event type '%s'" t

where the functions serialize : 'T -> string and deserialize : string -> 'T represent some serialization library like Json.NET. The purpose of the encoder functions is to embed domain events into a tupled representation, the first element being a string identifier for the event type, and the second potentially containing pickled payload data. Sending encoded events over the wire is then a relatively straightforward undertaking.

While this approach works fine with small examples, the boilerplate it introduces tends to become unwieldy as domain complexity grows. The keen-eyed reader might have noticed that I’ve inserted a couple of bugs in my decode function.

While one could argue that using techniques such as property based testing might be sufficient to catch such classes of bugs, the issue remains that making changes in event types generally comes with high maintenance. What if there existed a way to canonically represent union types in a way that is properly generic and serialization format agnostic?

The UnionContract Module

The TypeShape library that I maintain ships with a small module called UnionContract. The surface API is tiny, exposing only a single function and a couple of interfaces. At its core it defines a datatype generic program which accepts a serializer instance, represented by instances of the interface:

type IEncoder<'Format> =
    abstract Encode<'T> : value:'T -> 'Format
    abstract Decode<'T> : fmt:'Format -> 'T
    abstract Empty : 'Format

and generates functions capable of encoding and decoding union values in the sense described previously. We can equivalently express the above encoders using the code:

open System.Runtime.Serialization
open TypeShape.UnionContract
open Newtonsoft.Json

type CartEvent =
    | [<DataMember(Name = "cartCreated")>] CartCreated
    | [<DataMember(Name = "itemAdded")>] ItemAdded of ItemAdded
    | [<DataMember(Name = "itemRemoved")>] ItemRemoved of ItemRemoved
    | [<DataMember(Name = "cartCheckedOut")>] CartCheckedOut of CartCheckedOut
with
    interface IUnionContract // marker interface

// object  json string encoder used for union case payloads
let jsonEncoder =
    { new IEncoder<string> with
        member __.Empty = "null" // payload to be inserted in nullary cases
        member __.Encode(t : 'T) = JsonConvert.SerializeObject(t)
        member __.Decode(json : string) = JsonConvert.DeserializeObject<'T>(json) }

// creates a union contract encoder
let unionEncoder = UnionContractEncoder.Create<CartEvent, string>(jsonEncoder)

The UnionContractEncoder.Create method accepts a datatype generic encoder that pickles union case payloads into a fixed format type (in this case string), and generates an encoder that acts on the union level.

We can use the newly created encoder to encode and decode union instances:

unionEncoder.Encode(CartCreated)
// val it : EncodedUnion<string> = {CaseName = "cartCreated";
//                                  Payload = "null";}

unionEncoder.Encode(ItemAdded { skuId = "a" ; quantity = 2 })
// val it : EncodedUnion<string> = {CaseName = "itemAdded";
//                                  Payload = "{"skuId":"a","quantity":2}";}

Union instances can be reconstructed by applying the inverse function to the encoded unions:

unionEncoder.Decode { CaseName = "cartCreated" ; Payload = null }
// val it : CartEvent = CartCreated

So how does it all work? Under the hood, the implementation uses constructs from the TypeShape library to duplicate the logic of the original encode and decode functions in a datatype generic manner.

Plugging Serialization Formats

Serialization formats can be controlled by plugging different IEncoder implementations. For instance:

open Newtonsoft.Json.Linq

let jtokenEncoder =
    { new IEncoder<JToken> with
        member __.Empty = JValue.CreateNull() :> _
        member __.Encode(t : 'T) = JToken.FromObject t
        member __.Decode(t : JToken) = t.ToObject<'T>() }        

let jtokenUnionEncoder = UnionContractEncoder.Create<CartEvent,JToken>(jtokenEncoder)

produces an encoder that pickles event payloads as Newtonsoft JToken values.

Versioning Events

In the original example, suppose we want to alter the ItemRemoved event so that it additionally includes a quantityRemoved field like so:

type ItemRemoved = { skuId : string ; quantityRemoved : int}

Assuming that events using the original shape have already been persisted to the database, it is evident that this introduces a breaking change to the schematisation. Many databases typically used for event sourcing are of the “schemaless” variety, however as the author of Designing Data-Intensive Applications put it:

Document databases are sometimes called schemaless, but that’s misleading, as the code that reads the data usually assumes some kind of structure—i.e., there is an implicit schema, but it is not enforced by the database. A more accurate term is schema-on-read (the structure of the data is implicit, and only interpreted when the data is read), in contrast with schema-on-write (the traditional approach of relational databases, where the schema is explicit and the database ensures all written data conforms to it).

-Chapter 2, Data Models and Query Languages

So how do we ensure that union contracts enforce a version tolerant schema-on-read? I propose an approach adhering to the following set of principles:

1. Apply separation of domain types from DTOs.
2. Model DTOs using the UnionContract construct.
3. Make DTO union contracts append-only.
4. Freely evolve domain types as schema changes.
5. Push versioning and migration responsibility to the DTO layer.

Applying this to the above example would result in the following arrangement for domain events:

namespace Domain

type CartEvent =
    | CartCreated
    | ItemAdded of ItemAdded
    | ItemRemoved of ItemRemoved
    | CartCheckedOut of CartCheckedOut

and ItemRemoved = { skuId : string ; quantityRemoved : int}
...

whereas the contract type would look as follows:

namespace Contracts

type CartEventDto =
    | [<DataMember(Name = "cartCreated")>] CartCreated
    | [<DataMember(Name = "itemAdded")>] ItemAdded of ItemAdded
    | [<DataMember(Name = "itemRemoved")>] ItemRemovedV1 of ItemRemovedV1
    | [<DataMember(Name = "itemRemoved/v2")>] ItemRemovedV2 of ItemRemovedV2
    | [<DataMember(Name = "cartCheckedOut")>] CartCheckedOut of CartCheckedOut
with
    interface IUnionContract

and ItemRemovedV1 = { skuId : string }
and ItemRemovedV2 = { skuId : string ; quantityRemoved : int}
...

Notice how the two versions of ItemRemoved are defined as separate, explicitly qualified DTO union cases. On the other hand, the Domain event type only contains a single, canonicalized ItemRemoved case.

We need a fromDomain function to map domain events to DTOs:

let fromDomain = function
    | CartEvent.CartCreated -> CartEventDto.CartCreated
    | CartEvent.ItemAdded e -> CartEventDto.ItemAdded { skuId = e.skuId ; quantity = e.quantity }
    | CartEvent.ItemRemoved e -> CartEventDto.ItemRemovedV2 { skuId = e.skuId ; removedQuantity = e.removedQuantity }
    | CartEvent.CartCheckedOut e -> CartEventDto.CartCreated { checkoutDetails = e.checkoutDetails }

The opposite toDomain function is more interesting, as it contains migration logic:

let toDomain = function
    | CartEventDto.CartCreated -> CartEvent.CartCreated
    | CartEventDto.ItemAdded e -> CartEvent.ItemAdded { skuId = e.skuId ; quantity = e.quantity }
    | CartEventDto.ItemRemovedV1 e -> CartEvent.ItemRemoved { skuId = e.skuId ; removedQuantity = 1 }
    | CartEventDto.ItemRemovedV2 e -> CartEvent.ItemRemoved { skuId = e.skuId ; removedQuantity = e.removedQuantity }
    | CartEventDto.CartCheckedOut e -> CartEvent.CartCreated { checkoutDetails = e.checkoutDetails }

In this function, we choose to interpret “v1” ItemRemoved events as having removed quantity 1. By using the two functions in conjunction with the union encoder we obtain serialization/schema-on-read for the domain types as follows:

let serialize (e : CartEvent) = fromDomain e |> unionEncoder.Encode
let deserialize (c : EncodedUnion) = unionEncoder.Decode c |> toDomain

A nice property of this approach is that we are forcing any versioning and migration concerns outside of the domain, making business logic cleaner to work with. We have been using this pattern with success in a few of our systems.

Versioning Snapshots

This pattern is not strictly applicable to event serialization. We can also use it for versioning snapshot schemata:

type SnapshotV1 = { ... }
type SnapshotV2 = { ... }
type SnapshotV3 = { ... }

type SnapshotDto =
    | [<DataMember(Name = "snapshot/v1")>] SnapshotV1 of SnapshotV1
    | [<DataMember(Name = "snapshot/v2")>] SnapshotV2 of SnapshotV2
    | [<DataMember(Name = "snapshot/v3")>] SnapshotV3 of SnapshotV3 // current
with
    interface IUnionContract

let unionEncoder = UnionContractEncoder.Create<SnapshotDto,_>(jtokenEncoder)

We can then define our conversion functions, with a slight variation:

let fromDomain snapshot = SnapshotV3 snapshot

let toDomain = function
    | SnapshotV1 snap -> migrateFromV1 snap
    | SnapshotV2 snap -> migrateFromV2 snap
    | SnapshotV3 snap -> snap // current snapshot, no migration needed

Then as before, we obtain the serialization/migration functions by composition

let serialize (e : SnapshotV3) = fromDomain e |> unionEncoder.Encode
let deserialize (c : EncodedUnion) = unionEncoder.Decode c |> toDomain

Again, we have achieved pushing all versioning and migration concerns to the DTO layer of our codebase.

Conclusions

I have attempted to illustrate the utility of using F# Discriminated Unions as a means to encode code-first schematisations for “schemaless” (schema-on-read) datastores. The use of the TypeShape UnionContract module in conjunction with separating domain types from DTOs provides us with an effective pattern to isolate versioning and data migration concerns from core domain logic. The versioning logic itself is pure and as such highly amenable to testing. We have used this pattern effectively in multiple production systems across at least two different teams within Jet.

One of the interesting challenges when dealing with generic programming is testing. How could you possibly achieve extensive test coverage for a piece of code that works with arbitrary types? Suppose for instance that we have implemented a generic equality function:

val equals : 'T -> 'T -> bool

One of the properties we would expect this function to satisfy is reflexivity.
Put formally, the predicate

let reflexivity (t:'T) = equals t t

should return true for any value of any type.

The Standard Approach

Using a random testing tool like FsCheck, a common strategy to validate this would unfold as follows:

[<Property>]
let ``Int Reflexivity`` (x : int) = reflexivity x
[<Property>]
let ``String Reflexivity`` (x : string) = reflexivity x
[<Property>]
let ``2-Tuple Reflexivity`` (x : string * int) = reflexivity x
[<Property>]
let ``List Reflexivity`` (x : (string * int) list) = reflexivity x
[<Property>]
let ``List of List Reflexivity`` (x : (string * int) list list) = 
    reflexivity x
...

Expanding on tested types ad nauseam, until we finally convince ourselves that coverage is sufficient. But is it? How can we be sure that (string * int) list correctness implies correctness for (int * string) list? What about large tuple arities? We will always be forgetting something.

Generic Property Tests

I have been toying with the idea of generic property tests for quite a while now, but only the recent performance improvements in FsCheck 3 (currently in prerelease) have made this approach feasible. For starters, we will need to provide a rank-2 encoding for predicates:

type Predicate =
   abstract Invoke : 'T -> bool

Which permits declaration of generic predicate values (currently not a possibility with F# lambdas, which must be fixed on their argument types)

let reflexivity = 
    { new Predicate with
        member __.Invoke t = equals t t }

The goal is to use FsCheck in a way where generic predicates can be tested against random values of random types.

Defining a Type Algebra

Let’s start by defining the kind of types we would like to be testing. To do this we define a type algebra, or a “type of types”:

type TypeAlg =
    | BaseType of BaseType
    | List of TypeAlg 
    | Array of TypeAlg 
    | Option of TypeAlg 
    | Tuple of TypeAlg list

and BaseType = Bool | Byte | Int | String

Each instance of type TypeAlg represents an actual F# type. For instance, the value Tuple [BaseType Int; Option(BaseType String)] represents the type int * string option. As a first exercice, let’s try implementing a pretty-printer for the algebra:

let rec prettyprint ta =
    match ta with
    | BaseType Bool -> "bool"
    | BaseType Byte -> "byte"
    | BaseType Int  -> "int"
    | BaseType String -> "string"
    | List element -> sprintf "(%s) list" (prettyprint element)
    | Array element -> sprintf "(%s) []" (prettyprint element)
    | Option element -> sprintf "(%s) option" (prettyprint element)
    | Tuple elements -> 
        elements 
        |> Seq.map prettyprint 
        |> String.concat " * " 
        |> sprintf "(%s)"

Importantly, it is possible to map any TypeAlg representation to its corresponding System.Type runtime instance like so:

let rec meaning ta : System.Type =
    match ta with
    | BaseType Bool -> typeof<bool>
    | BaseType Byte -> typeof<byte>
    | BaseType Int  -> typeof<int>
    | BaseType String -> typeof<string>
    | List element -> typedefof<_ list>.MakeGenericType(meaning element)
    | Array element -> (meaning element).MakeArrayType()
    | Option element -> typedefof<_ option>.MakeGenericType(meaning element)
    | Tuple [] -> typeof<unit>
    | Tuple elements -> 
        elements 
        |> Seq.map meaning 
        |> Seq.toArray 
        |> FSharp.Reflection.FSharpType.MakeTupleType

We can use TypeShape to take that semantic mapping one step further: bring the type into scope as a generic argument.

open TypeShape.Core

let visitTAlg (visitor : ITypeShapeVisitor<'R>) (tAlg : TypeAlg) : 'R =
    let sysType : Type = meaning tAlg
    let shape : TypeShape = TypeShape.Create sysType
    shape.Accept visitor

We can verify the behaviour by running

let getType = 
    { new ITypeShapeVisitor<System.Type> with 
        member __.Visit<'T>() = typeof<'T> }
    |> visitTAlg

getType (BaseType Int) // typeof<int>
getType (Option (BaseType (String)) // typeof<string option>

Putting it all Together

Let’s now see how we can use this technique to obtain a random tester for generic predicates. Consider the following function:

open FsCheck

let checkTAlg (predicate : Predicate) (tAlg : TypeAlg) : bool =
    printfn "Testing %s" (prettyprint tAlg)
    let checker = 
        { new ITypeShapeVisitor<bool> with 
            member __.Visit<'T>() =
                Check.QuickThrowOnFailure<'T -> bool> predicate.Invoke 
                true }
    
    visitTAlg checker tAlg

The implementation accepts a generic predicate and a type representation, uses TypeShape to bring the type into scope as a type variable, then calls FsCheck with the predicate instantiated to the reified type.

The key observation for converting this function into a generic property test is that TypeAlg is an algebraic data type, and FsCheck is capable of generating random instances for type out of the box:

let checkGeneric (predicate : Predicate) =
    Check.QuickThrowOnFailure<TypeAlg -> bool>(checkTAlg predicate)

We are now ready to random test our reflexivity property:

checkGeneric reflexivity

which yields the following output:

Testing (bool) []
Ok, passed 100 tests.
Testing byte
Ok, passed 100 tests.
Testing ((bool) option) list
Ok, passed 100 tests.
Testing bool
Ok, passed 100 tests.
Testing (string * byte)
Ok, passed 100 tests.
Testing ((string) option) option
Ok, passed 100 tests.
Testing ((bool * ((((((()) []) []) option) option) list) [] * byte * int * string * string * int * bool * int * int * int * byte)) option
Ok, passed 100 tests.
...

In effect this call will test 100 randomly generated types with 100 randomly generated values each.

Conclusions

Applying the above technique when testing generic programs code has proven to be extremely effective. It has allowed me to discover both implementation bugs of the generic programs themselves, as well as obscure bugs of the core TypeShape library. My previous, handwritten test suite had failed to catch any of those issues. If interested, have a look at this source file for an example of a more complete implementation of the technique.

During a recent conversation with a group of F# developers, I started making the case for recursion and its importance in day-to-day programming. My peers reacted with surprise to this opinion of mine, responding that they thought that recursion is an inherently inefficient way of defining programs.

We are taught this rule when studying procedural languages: “for optimal results, just use iteration”. In functional languages however, this is not necessarily true: tail-recursive functions are optimized into imperative loops at compile time and most recursive functions can be readily transformed into tail-recursive workflows by applying accumulators or CPS. These FP fundamentals are what make the functional paradigm a feasible alternative to the imperative style.

I was thus legitimately surprised to discover that working F# programmers carried this attitude towards recursion, which made me wonder whether this could be an artifact of how the language is being taught to FP newcomers. I researched some of the popular online material and did a bit of asking around which seemed to confirm my suspicion: there exists a tendency for de-emphasizing recursion in beginner F# educational material. An important reason is that the topic of recursion itself can appear puzzling and counter-intuitive to beginners: quoting Graham Hutton

Defining recursive functions is like riding a bicycle: it looks easy when someone else is doing it, may seem impossible when you first try to do it yourself, but becomes simple and natural with practice.

Omitting recursion can also be justified by a desire to appear pragmatic; recursion has a reputation for being too academic, a mathematical trivium that is only useful when defining Fibonacci numbers but not relevant in real code. Algorithms should be declared by composing available combinators, and if everything fails we can always fall back to the imperative style. Recursion is relegated to the “Advanced” chapters, bundled together with other academic curiosities such as call/cc and catamorphisms.

An Example

While there are merits in this stance, I claim that avoiding recursion entirely in expression-based languages comes with some very important limitations. I will try to illustrate why using an example. Consider the core combinator

val List.tryFind : ('T -> bool) -> 'T list -> 'T option

which performs linear searches on its supplied list, returning the first element that happens to satisfy the supplied predicate. This is a simple yet extremely useful combinator that is often finding use in F# codebases. It works very well for most applications, assuming our predicate is a regular lambda.

But what happens if the predicate is of type 'T -> Async, in other words asynchronous? We would probably require a variation of tryFind, namely

val tryFindAsync : ('T -> Async<bool>) -> 'T list -> Async<'T option>

which however is not available the core library. In such circumstances, F# developers will have to improvise.

As an exercise, let’s attempt to provide a good implementation that avoids recursion. A novice user would quickly end up with the following solution:

let tryFindAsync (pred : 'T -> Async<bool>) (inputs : 'T list) =
    async { return List.tryFind (pred >> Async.RunSynchronously) inputs }

which is evidently a misguided solution, since it invalidates the purpose of asynchrony.

The requirement for asynchrony could still be satisfied using smarter manipulation of generic combinators, as seen in the following example:

let tryFind (f : 'T -> Async<bool>) (ts : 'T list) =
    let folder acc t = async {
        let! result = acc
        match result with
        | Some _ -> return result
        | None ->
            let! success = f t
            return if success then Some t else None
    }

    List.fold folder (async.Return None) ts

In this case, we are folding over asynchronous computations, so the final result is a non-blocking asynchronous workflow that can be consumed accordingly. There are however two problems with this approach:

1. The solution is too smart for its own good. Sure, folding over functions feels good to the person that came up with it, however there is a nontrivial cognitive overhead associated with what should be a very simple task. In the context of a bigger team, such heroics aren’t appreciated.
2. More importantly, fold operations always traverse the entire input list. The point of tryFind is that it should stop as soon as a result is found. By delegating iteration to other combinators, we lose the ability to tune aspects of control flow. Assuming our input type allowed for infinite lists (for instance IEnumerable), this approach would necessarily result in non-terminating computation.

An Imperative Solution

Let us now try addressing the same problem using the imperative style. First, here’s how it could be defined elegantly using C#:

async Task<Option<T>> TryFindAsync<T>(Func<T, Task<bool>> predicate, IEnumerable<T> inputs)
{
    foreach (var t in inputs)
        if (await predicate(t)) return Option.Some(t);
    
    return Option.None<T>();
}

What happens if we attempt to port this implementation to F#? First of all, F# is an expression-based language, which means that return keywords (in the imperative sense) are not permitted. Rather, we need to introduce additional variables to simulate breaks:

let tryFindAsync (predicate : 'T -> Async<bool>) (ts : 'T list) = async {
    let mutable result = None
    let mutable ts = ts
    while Option.isNone result && not (List.isEmpty ts) do
        let head :: tail = ts
        let! r = predicate head
        if r then result <- Some head
        else ts <- tail

    return result
}

Few would disagree with the conclusion that this solution is ugly and easy to get wrong. The lack of return, break and continue constructs in expression-based languages is the primary reason why an imperative approach is awkward here.

Real-Word Recursion

This is precisely where recursion comes in handy. It can be used to effectively emulate any sort of imperative break in expression-based programs:

let rec tryFind (f : 'T -> Async<bool>) (ts : 'T list) = async {
    match ts with
    | [] -> return None
    | head :: tail ->
        let! r = f head
        if r then return Some head
        else return! tryFind f tail
}

Similar examples can be provided that illustrate how break and continue constructs can be emulated using recursion.

Conclusion

When working with expression based languages, recursion is an essential tool for achieving control flow patterns typically only attainable via imperative constructs. In the context of F#, working programmers can only benefit from acquainting themselves with the standard syllabus of common recursion patterns commonly used in FP languages.

Point-free programming (or point-less programming, for the more cynically inclined) is a paradigm that advocates the formulation of programs by means of function composition. In the point-free style programs avoid explicitly nominating function arguments (or “points”), deriving instead complex function definitions by means of applying higher-order combinators on simpler functions.

To give an F# example, the code

let f xOpt =
    match xOpt with
    | Some x when x >= 0. -> Some(sqrt x)
    | _ -> None

can be refactored into the following one-liner:

let f = Option.map sqrt << Option.filter ((<=) 0.)

This is an extremely powerful technique, deeply rooted in concepts that are foundational to mathematics and logic. It fully embraces the realization that most meaningful concepts can be defined in terms of functions and function composition.

A Taste of Category Theory

If we were trace the influence (and indeed, sexiness) of the point-free style to a single origin, then that would undoubtedly be category theory. Category theory is the field of mathematics that (roughly) deals with the the study of function composition in the abstract.

A category consists of abstract functions (or morphisms, or “arrows”) that have an origin and destination (or domain and codomain, or “argument type” and “return type”). Morphisms can be composed in a way that certain laws are satisfied. Importantly, categories carry a notion of function equality. Ultimately, all meaningful properties of a category are expressed in terms of that equality. Category theory allows for the study of entities that are not functions in the strict sense, but which nevertheless behave like functions.

This idea is powerful enough to serve as a foundation for the whole of mathematics, and then some. Its application has also been fruitful in logic and computer science, particularly in the field of denotational semantics, where it has been used to define domains not attainable using regular set theory.

Thus the point-free style isn’t just the natural way of working with categories, it is really the only way (which is kind of the point). Whereas sets have elements and types have terms, there is no corresponding concept baked into categories in the general case (thunks being the next best thing). This has interesting ramifications in terms of expressivity. To illustrate, consider the following expression from the typed lambda calculus:

This otherwise simple expression is defined in category theory as follows:

rendered as the expression

where

• denotes the identity morphism on .
• denotes the diagonal morphism.
• denotes the product bifunctor.
• denotes the associativity isomorphism on products.

If the above definition seems abstruse, it’s because it is. Two points particularly add to the complexity of the point-free definition:

• The requirement that is passed as an argument twice: we are forced to simulate this duplication by precomposing with the diagonal (rendered using the lambda calculus).
• Our inability to pattern match and rearrange inputs: arguments have to be meticulously juggled around using associativity transformations.

Ultimately, what was a lambda expression that could be read and understood in seconds has been turned into an expression that takes minutes to grasp.

The point of this exercise is to illustrate how the lambda calculus with pattern matching (or set theory for that matter) is superior to the point-free style in terms of expressive efficiency. Not only does it naturally incorporate the point-free style, but it extends far beyond its capacity to concisely express complex definitions. It goes on to show that unless your work requires reasoning about large categories, you are potentially better off steering clear from an exclusively point-free style.

Programming Take-Aways

So how does this all translate to our coding practices? Let us bring back that F# example referenced at the beginning of the article:

let f xOpt =
    match xOpt with
    | Some x when x >= 0. -> Some(sqrt x)
    | _ -> None

versus

let f = Option.map sqrt << Option.filter ((<=) 0.)

I claim that the first implementation provides the simpler and more idiomatic solution, for many reasons:

• it’s easiest to read and understand.
• it assigns a name to the argument, which is exposed as part of the type signature.
• it provides the most efficient implementation, avoiding gratuitous allocations/invocations of lambda objects.
• it allows setting of breakpoints, a crucial ability when debugging large codebases.

The central thesis of this article then is more-or-less a reflection of the conclusions drawn from the previous section: ML affords a style of programming that both incorporates and is more expressively efficient than strict function composition. Point-free implementations also tend to be brittle, with slight alterations to either implementation or type signature often prompting substantial rewrites and introduction of new classes of combinators.

These observations can be extended to function usage patterns that are not point-free in the strict sense. Let’s consider a very simple example:

let x = pair |> fst

This is a very common way for deconstructing tuples. It works well, as long as our tuple is indeed a pair. When different arities come into play, it often is necessary to introduce non-standard projection functions:

let proj1Of3 (x,_,_) = x
let proj2Of3 (_,y,_) = y
let proj3Of3 (_,_,z) = z

List.exists (proj2Of3 >> (=) 3)

This approach has a few problems: each tuple type requires its own set of projector definitions, and the introduction of non-standard combinators adds comprehension overhead. The idiomatic solution afforded by ML does not suffer from either problem:

let x,_ = pair
List.exists (fun (_,y,_) -> y = 3)

The same can be said about non-standard combinators like flip, curry and uncurry. For example

let flip f = fun x y -> f y x

Is a combinator commonly used in functional pipelines like the following:

List.filter ((=) 0 << flip (%) 2)

Again, this implementation suffers from similar problems: it is hard to comprehend; it relies on a non-standard combinator; supporting combinators for every permutation of curried parameters is intractable, with possible combinators for functions accepting curried arguments. I contend that code can be greatly simplified in the general case by employing a lambda literal:

List.filter (fun n -> n % 2 = 0)

The Value of Computation Expressions

“Monad” in the context of programming is a term that carries multiple meanings. First and foremost, a monad denotes a type augmented with a set of functions that satisfy the monad laws. Secondarily, it refers to the capacity of a programming language to provide syntactic sugar for monad instances. A language can have monadic types without syntactic sugar support and conversely, a syntactic monad does not necessarily satisfy the monad laws.

The importance of the latter kind of monad cannot be overstated. It provides a mechanism for lifting user-defined combinators into language-integrated expressions. The impact on readability is dramatic. Consider for instance an expression using the option monad:

option {
   let! x = Some 1
   let! y = Some 2
   let! z = Some 3
   return (x,y,z)
}

which desugars into

Some 1
|> Option.bind (fun x ->
    Some 2
    |> Option.bind (fun y -> 
        Some 3
        |> Option.bind (fun z -> Some(x,y,z))))

Notice that the nesting of the bind operations is essential due to scoping considerations: the final operation depends on all three bindings, thus converting this to a flattened pipeline is not possible unless we somehow accumulate the arguments:

Some 1
|> Option.bind (fun x -> Some (x,2))
|> Option.bind (fun (x,y) -> Some (x,y,3))

These examples serve to demonstrate that extended usage of monadic combinators without syntactic sugar support becomes intractable as complexity of workflows increases.

F# computation expressions embrace the significance of syntax, by design: rather than being tied to monads in particular, they provide a general-purpose mechanism for overloading almost every language keyword. Computation expressions can be monads, sequence builders, imperative DSLs, query languages or anything in between. Their goal is to abstract away the noise of combinators and enable DSLs that can be written using human-readable expressions. We can write

let f xs =
    [ for x in xs do
        let y = x + 1
        if y % 5 = 0 then 
          yield string y ]

instead of

let f =
    List.map ((+) 1)
    >> List.filter (flip (%) 5 >> (=) 0)
    >> List.map string

It is this pragmatic design that explains the resounding success of F# async. Computation expressions liberate us from the burden of doing asynchronous programming using callbacks and rather let us write it as if it were synchronous. In that sense, I must say that I am puzzled by a certain tendency within the F# community to use Kleisli-style combinators on top of async:

let (>=>) (f : 'a -> Async<'b>) (g : 'b -> Async<'c>) =
    fun a -> async.Bind(f a, g)

let catch (h : exn -> Async<'b>) (f : 'a -> Async<'b>) =
    fun a -> async.TryWith(f a, h)

async.Return << serialize
>=> sendRequest Post "/foo"
>=> async.Return << deserialize
|> catch (function :? IOException -> return None 
                   | _ -> failwith "unexpected error")

I contend that this technique is a regression, in fact just a fancy way of doing async programming using explicit callbacks. Compare for instance with a slightly similar snippet using TPL:

Task.FromResult(x)
    .ContinueWith(fun x -> serialize x.Result)
    .ContinueWith(fun req -> sendReqAsync Post "/foo" req.Result)
    .ContinueWith(fun res -> deserialize res.Result)
    .ContinueWith(fun res ->
        if res.IsFaulted && res.Exception :? IOException then None
        else res.Result)

The power of async workflows lies in their simplicity. Compare the samples above with idiomatic async:

async {
    try
        let request = serialize x
        let! response = sendRequest Post "/foo" request
        return deserialize response 
    with :? IOException -> return None }

By relying on the compiler to tuck away the visual noise of callbacks, we obtain clean, readable, flexible, composable and debuggable code. Embedded pattern matching, nested expressions, lexical scoping and recursion provide a mix of tools that is strictly more expressive and concise than any ad-hoc forest of point-free monadic combinators.

Conclusion

It is not the case that the point-free style is useless. In fact, libraries often adopt the point-free style out of performance considerations. Good examples are parser combinators and pickler combinators, and there are more. These typically make the informed trade-off of sacrificing readability in the interest of eliminating allocations typically associated with expression builders. In rare cases there can even be point-free DSLs that are actually legible in the large. However the utility of adopting this approach always carries a big burden of proof, and should not be motivated merely out of stylistic considerations.

F# is a functional-first programming language that comes with a substantial object-oriented feature set. It is so feature-complete in fact, that almost any C# class can be ported over to F# code with little substantial alteration.

However significant, this subset of the language is seeing limited appreciation from the community, which I suspect is partly fuelled by the known criticisms of OOP and partly by a desire to be different than C#. After all, this is a functional-first language so we can just replace all our classes with functions. There is also the opinion that OOP in F# merely serves as a compatibility layer for .NET, so it’s really only there to cover those unfortunate scenarios of having to use a library that accepts interfaces.

Enabling Abstraction

One of the most important aspects of maintaining a nontrivial codebase is controlling complexity. Complexity can be contained by partitioning code into logically standalone components whose implementation details are hidden behind appropriately designed abstractions. In his excellent Solid and Functional article, Vesa Karvonen argues that selecting the correct abstraction is a hard problem, and that functional programming is no silver bullet in dealing with that. This resonates a lot with me, and I strongly encourage everyone to read the full article.

That said, Vesa is framing the article in Standard ML which supports a full-blown module system. Modules can be abstracted using signatures or they can be parameterized by other modules using functors. Modules are the predominant means of abstraction in the ML ecosystem. In Haskell, it is type classes and higher-kinded types. In F#, modules are intentionally stripped of any complicated features, effectively functioning as a mere namespacing construct.

My claim is that there are inherent limits to what can be expressed using just F# modules and functions, in terms of enabling good abstraction. Luckily, we can always make use of the next best thing, which is F# OO. The thesis of this article is that strategically admitting elements of OO in an F# codebase significantly improves quality and maintainability. While I cannot conclusively prove this within the confines of a single blog post, I will try to provide hints as to why this is.

Classes as Value Parametric Modules

It is often the case that an API exposed through a module must be context aware. Typically F# developers address this by adding extra parameters in every function:

module MyApi =
    let function1 dep1 dep2 dep3 arg1 = doStuffWith dep1 dep2 dep3 arg1
    let function2 dep1 dep2 dep3 arg2 = doStuffWith' dep1 dep2 dep3 arg2

While this does work well in simple cases, it does not scale nicely as dependencies increase. It would typically prompt the developer to group arguments in context records:

type MyApiContext = { Dep1 : Dep1 ; Dep2 : Dep2 ; Dep3 : Dep3 }

module MyApi =
    let function1 (ctx : MyApiContext) arg1 = doStuffWith ctx.Dep1 ctx.Dep2 ctx.Dep3 arg1
    let function2 (ctx : MyApiContext) arg2 = doStuffWith' ctx.Dep1 ctx.Dep2 ctx.Dep3 arg2

This complicates the implementation even more both in the definition site and in the consumption site. In practice, you either end up with one context type per component or one God context for the entire application. Even more importantly, this approach often violates encapsulation concerns, pushing the burden of gathering dependencies to the consumers of the API, every single time they do consume the API. Partial application also does little to address any of these concerns in nontrivial contexts.

Less experienced developers might be prompted to do something even worse: lift dependencies to module values.

module MyApi =
    let dep1 = File.ReadAllText "/Users/eirik/connectionstring.txt"
    let dep2 = Environment.GetEnvironmentVariable "DEP_2"
    let dep3 = Random().Next()

    let function1 arg = doStuffWith dep1 dep2 dep3 arg
    let function2 arg = doSutffWith dep1 dep2 dep3 arg

This is bad for many reasons: it makes the API reliant on global state, introduces unneeded side-effects, and pushes app configuration concerns deep inside the guts of our codebase. What’s more, module value initialization compiles to a static constructor for the entire compilation unit so the exact moment of execution is largely unpredictable. Initialization errors manifest as TypeInitializationExceptions which are difficult to debug.

Contrast the situation above with the elegance afforded by a plain old class:

type MyParametricApi(dep1, dep2, dep3) =
    member __.Function1 arg1 = doStuffWith dep1 dep2 dep3 arg1
    member __.Function2 arg2 = doStuffWith' dep1 dep2 dep3 arg2

An API object could be created once at application initialization, or as many times required depending on context. It’s also more amenable to testing. I should add that this approach is essentially just as “functional” as the approaches above, since it’s merely composing dependencies to expose a context-sensitive API. Importantly, it achieves this in a much simpler way both in the definition site and consumption site, which pays great dividends if realized in big codebases.

Expressive APIs

An important attribute of method-based APIs is that they allow for greater expressive power, in two important ways:

1. Named/Optional parameters: unlike OCaml, whose functions support out-of-order named argument passing and omitted optional arguments, F# functions support neither. Luckily, we can do this using F# methods. I find this to be an immensely powerful tool when exposing non-trivially parameterizable functionality. A function that explicitly accepts 10 optional parameters is not acceptable; a method that accepts 10 optional arguments works like a charm.
2. Method overloading: because function names like connect' and bind2 are simply not good enough when exposed in a public API.

More Powerful Types

The type system afforded by .NET is strictly more powerful than what can be expressed using modules and functions. For example, the interface

type Scheduler =
    abstract Run<'T> : Async<'T> -> 'T

encodes a kind of function that cannot be expressed in terms of proper F# lambdas. When combined with subtyping, it is possible to effectively encode existential types and Rank-N polymorphism. Even GADTs are possible, with minimal augmentations of the type system.

In practice, it is possible to leverage that additional power very effectively. In fact, F# makes it easy to define generic function literals using object expressions. This is also how the TypeShape library has been made possible.

Abstracting Modules

Functions are the unit of abstraction in F#, but that unit is often insufficient when abstracting APIs. This prompts developers to adopt an approach where abstract APIs are surfaced as either records or tuples of functions:

type Serializer =
    {
        Serialize : bool -> obj -> string
        Deserialize : bool -> string -> obj
    }

According to the F# design guidelines, use of records for building APIs is discouraged and recommends using regular interfaces instead.

I strongly agree with this recommendation for a multitude of reasons: interfaces are more powerful since they support generic methods, named arguments and optional arguments. An interface is less likely to be defined in terms of closures, making it easier to reason about when viewing from a debugger.

So the example above could be rendered as an interface like so:

type Serializer =
    abstract Serialize<'T> : preserveRefEq:bool -> value:'T -> string
    abstract Deserialize<'T> : preserveRefEq:bool -> pickle:string -> 'T

The most important aspect of this approach is readability. It is easier for a consumer of this interface to anticipate what the purpose of each argument is, in the same way that it is easier to understand a record of functions over a tuple of functions.

Representing Illegal State

A lot of proverbial ink has been spent describing how we should strive to make illegal states unrepresentable. However, I do fail to see how this could be fully realized given that the functional core of F# only consists of algebraic data types. Take for example an oft-quoted email type:

type Email = Email of string

The following values are valid instaces of type Email:

Email null
Email "John Smith"
Email "eirik@foo.bar'; DROP TABLE dbo.Users"

If we truly care about illegal states, the obvious alteration to the type above ought to be the following

type Email = private | Email of string
with
    member this.Address = let (Email addr) = this in addr
    static member TryParse(address : string) =
        if isValidEmail address then Some(Email address)
        else None

But really, this is a just a class encoded by a union. The implementation below is simpler:

type Email private (address : string) =
    member __.Address = address
    static member TryParse(address : string) =
        if isValidEmail address then Some(Email address)
        else None

NB the previous implementation might in fact be warranted in cases where free structural equality or comparison are needed. But for all intents and purposes, both approaches effectively subscribe to OO-style encapsulation.

OO And Purity

The relationship between OO and purity can be a frequent avenue for misconception. Occasionally someone will claim that by admitting objects we are ipso facto forsaking purity. On the contrary, I do claim that these really are orthogonal concerns. Just as a lambda is capable of producing side-effects, objects can be designed for purity. Good examples of this are Map and Set in the core library. The lambda is really just an abstract class with a single virtual method and lots of syntactic sugar. There is nothing fundamentally setting it apart from objects once you exclude the syntactic aspect.

Conclusions

So, is this a call to go full-blown OO in F# projects? Should we be digging up our old GoF copies? Are design patterns up there in the functional curriculum together with profunctor optics? Are inheritance and class hierarchies sexy again? No!

I am in fact proposing that there is a third way, where functional and OO components coexist, with one paradigm complementing the other. This is hardly a new idea. Quoting from the F# design guidelines:

F# is commonly called a functional-first language: object, functional and imperative paradigms are all well supported, but functional programming tends to be the first technique used. Many of the defaults of F# are set up to encourage functional programming, but programming in the other paradigms is effective and efficient, and a combination is often best of all. It is a common misconception that the functional and object programming methodologies are competing. In fact, they are generally orthogonal and largely complementary. Often, functional programming plays a stronger role “in the small” (e.g. at the implementation level of functions/method and the code contained therein) and object programming playe a bigger role “in the large” (e.g. at the structural level of classes, interfaces, and namespaces, and the organization of APIs for frameworks).

In my 6 years of working with F#, my style has gradually shifted towards embracing this approach. A few examples:

• I typically write the implementation of a large component in the functional style behind a private module, then expose its public API as part of a standalone class. I find that method-based APIs are friendlier to consumers unfamiliar with the implementation.
• I use records and unions for encoding internal representations and classes for encapsulating publicly visible instances. A very good example of this is the F# map implementation.
• I rarely expose records and unions as part of a public API unless it is abundantly evident that all possible instances for the given types are valid in their context of use. This does not happen often in my experience.
• If a module is exposed as part of a public API, care must be taken so that the number of arguments is small and behaviour can be predicted by reading the type signature of the function alone. The core List and Array modules are a good example. Avoid using modules to expose complex functionality like the Async API.

I remember reading a few years back Simon Cousins’ NOOO manifesto, which stands for Not Only Object-Oriented development. In retrospect I find this to be an excellent name for a manifesto, if only because “Not Only OO” is not the same thing as “No OO”. So here’s a proposal to revive that manifesto, perhaps with the understanding that “Not Only OO” also implies “Not Only FP” in the context of F#.

Purely functional programming according to wikipedia

designates a programming paradigm that treats all computation as the evaluation of mathematical functions. Purely functional programing may also be defined by forbidding changing state and mutable data.

The importance of the purely functional approach cannot be overstated: it eliminates entire classes of mutation-related bugs; encourages composable abstraction; pure code can be reasoned about equationally; the explicit segregation of side-effects acts as a forcing function for better abstraction. At the same time, immutable persistent data structures can be cheaply incremented while shared safely across multiple threads. Pure programs also admit compile-time optimizations that would be tricky to achieve in the presence of state.

Benefits aside, purity is an attribute of expressions and their formal semantics. A pure program would still end up executing on regular computer hardware, where it could demonstrate the following effects: high CPU utilization, excessive heap allocations, stack overflows, divizion by zero errors, etc. Thus the connection of pure code to functions of the mathematical variety should not be considered a literal one, otherwise all correct Fibonacci implementations would be equal by virtue of extensionality. Being able to reason how code —pure or otherwise— executes on the underlying hardware is critically important for the working programmer.

An ML Tradition

Transforming purely functional declarations into equivalent, optimal imperative code is a holy grail, still very much a topic of active research. In the general case though, performance can only be attained by forsaking purity. This is very much compatible with the ML philosophy, which has traditionally embraced imperative features in its language core. Quoting from Real World OCaml

Pure code is the default in OCaml, and for good reason—it’s generally easier to reason about, less error prone and more composable. But imperative code is of fundamental importance to any practical programming language, because real-world tasks require that you interact with the outside world, which is by its nature imperative. Imperative programming can also be important for performance. While pure code is quite efficient in OCaml, there are many algorithms that can only be implemented efficiently using imperative techniques.

OCaml offers a happy compromise here, making it easy and natural to program in a pure style, but also providing great support for imperative programming.

This also applies particularly well to F#, an OCaml dialect for the .NET framework. In my personal experience, performance gains when switching from purely functional to imperative code in F# can be particularly dramatic. Strategically adopting imperative implementations in performance-critical components is often vital to ensuring sustainability of a system.

Imperative Programming done right

So what does this all mean? Should we just give up on purely functional code in the interest of performance? Is F# really just a way to write C# programs in ML-style syntax?

Well, not really. I do claim though that there is a sweet spot where impure features can be utilized to combine the benefits of pure FP with a lot of the efficiency of procedural code. Defining that sweet spot is hard, however I cannot think of a more concise example than Nessos Streams, which provides a highly efficient functional streams implementation in just over 40 lines of code. Other examples could include FParsec and Hopac, whose core implementations have been written in C# out of performance considerations.

If one had to nominate a key guiding priciple for using imperative features in F# code, then surely we would single out referential transparency. Very roughly, a function is referentially transparent if it behaves like a pure function, even if its implementation might use imperative constructs. For example, the function

let incr (cell : int ref) : unit = cell := !cell + 1

is not referentially transparent because substituting a call to incr with the the result of the computation is not a behaviour-preserving transformation, in general.

We can still use imperative features to define functions that are in fact referentially transparent. A good example is implementing groupBy for lists. A purely functional groupBy could be written as follows:

let groupBy (proj : 'T -> 'Key) (ts : 'T list) : ('Key * 'T list) list =
    let folder (map : Map<'Key, 'T list>) (t : 'T) =
        let key = proj t
        let grouped = defaultArg (Map.tryFind key map) []
        Map.add key (t :: grouped) map

    ts
    |> List.fold folder Map.empty
    |> Map.toList
    |> List.map (fun (k,v) -> k, List.rev v)

This implementation may be pure, however performance-wise it is not ideal. We can still produce a more efficient, imperative equivalent of the same function:

let groupBy' (proj : 'T -> 'Key) (ts : 'T list) : ('Key * 'T list) list =
    let dict = new Dictionary<'Key, ResizeArray<'T>>()
    for t in ts do
        let key = proj t
        let mutable array = null
        if not <| dict.TryGetValue(key, &array) then
            array <- new ResizeArray<'T>()
            dict.Add(key, array)
        array.Add t

    dict
    |> Seq.map (function KeyValue(k,v) -> k, Seq.toList v)
    |> Seq.toList

The second function provides order-of-magnitude performance gains, but is also referentially transparent: it can be substituted with the pure implementation or the resulting value without affecting behaviour of the overall program. In fact, this approach very much reflects how the core library implements its own functions.

Conclusion

Purely functional programming in F# provides a very effective means of reasoning about code, however in the interest of efficiency it is often preferable to leverage the imperative aspects of the language. When done carefully, it can result in better performing code that sacrifices few if any of the benefits of the purely functional approach.

In fact, my claim is that this is very much the idiomatic way of using ML in general and F# in particular. Pretending that F# is a purely functional language à la Haskell is highly counterproductive, particularly when authoring production-grade projects.