more on Monoids in F# – exploiting static constraints

Just a quick follow up on yesterdays post on Monoids.

Maybe you did not like the way the structure of the monoids was passed around using a simple record and indeed there is a way to define the Z and ++ as generic operators by exploiting Statically Resolved Type Parameters in F#.

As far as I know this was first mentioned here and there is a great project on github using this FsControl.

Rewriting some of the instances this way can look something like this:

open FsCheck
open FsCheck.Xunit

type Neutral() =
    static member val Instance = Neutral()
        
    static member Neutral (_:list<_>, _:Neutral) = []
    static member Neutral (_:'a->'a,  _:Neutral) = id

    static member inline Invoke() = 
        let inline neut  (a:^a, b:^b) = 
            ((^a or ^b):(static member Neutral:_*_->_) 
             b, a)
        let inline neut' (a:'a) = 
            neut (a, Unchecked.defaultof<'b>) :'b
        neut' Neutral.Instance

type Operator() =
    static member val Instance = Operator()
        
    static member Op (a:list<_>, b:list<_>) = a @ b
    static member Op (f:'a->'a,  g:'a->'a)  = f >> g

    static member inline Invoke (a:'a) (b:'a) : 'a = 
        let inline op (_:^M, x:^v, y:^v) = 
            ((^M or ^v) : (static member Op:_*_->_) x, y)
        op (Operator.Instance, a, b)

[<AutoOpen>]
module Operators =
    let inline Z ()     = Neutral.Invoke ()
    let inline (++) x y = Operator.Invoke x y

type NonNullString = 
    NNS of string with
    static member Neutral (_,_)          = NNS ""
    static member Op      (NNS a, NNS b) = NNS (a+b)

type Prod =
    Prod of int with
    static member Neutral (_,_)            = Prod 1
    static member Op      (Prod a, Prod b) = Prod (a*b)

type Generators() =
    static member NonNullString : Arbitrary<NonNullString> =
        let nns s = 
            if System.String.IsNullOrEmpty s 
            then "" 
            else s
            |> NNS
        { new Arbitrary<NonNullString>() with
            member __.Generator = 
                Arb.generate |> Gen.map nns 
        }


module ``check Monoid axioms for int-Lists`` =
    type T = list<int>

    [<Property>]
    let ``[] is the neutral element``(v : T) =
        Z() ++ v = v && v ++ Z() = v

    [<Property>]
    let ``concatenation is commutative``(a : T, b : T, c : T) =
        a ++ (b ++ c) = (a ++ b) ++ c


[<Xunit.ArbitraryAttribute(typeof<Generators>)>]
module ``check Monoid axioms for NonNullString`` =
    type T = NonNullString

    [<Property>]
    let ``"" is the neutral element``(v : T) =
        Z() ++ v = v && v ++ Z() = v

    [<Property>]
    let ``concatenation is commutative``
        (a : T, b : T, c : T) =
            a ++ (b ++ c) = (a ++ b) ++ c

module ``check Monoid axioms for Prod`` =
    type T = Prod

    [<Property>]
    let ``1 is the neutral element``(v : T) =
        Z() ++ v = v && v ++ Z() = v

    [<Property>]
    let ``multiplication is commutative``
        (a : T, b : T, c : T) =
            a ++ (b ++ c) = (a ++ b) ++ c

You can find a gist containing the relevant code here.

my take on it

First let me make clear that I love how those guys managed to put this all together! – this is a major hack of F# and it’s type-system. It’s one of the most clever thing I saw using F# and I am really impressed by all Gustavo did there.

But for me this is just to much boiler-plate only to get simulated type-class support that really should be there in the language itself (or maybe better: a ML-like module system). In the end at this point this is just used to get function-overloads based on type (a great feature). At the moment I prefer to use modules (like List.map, Option.map) – yes the compiler could know this but for me it’s no big deal.