Cook Computing

F# Type Inference

October 25, 2011 Written by Charles Cook

F# Type inference might just be syntax sugar as Brian McNamara puts it in his post Overview of type inference in F#, but it's sweetness is very appealing. I thought this when I saw slide 12 in Tomas Petricek's and Phil Trelford's presentation Turning to the Functional Side With F#. Two C# functions:

public static IEnumerable<R> Map<T, R>(this IEnumerable<T> xs, Func<T, R> f)
{
    foreach (var x in xs)
        yield return f(x);
}

public static R Reduce<T, R>(this IEnumerable<T> xs, R init, Func<R, T, R> )f
{
    var current = init;
    foreach (var x in xs)
        current = f(current, x);
    return current;
}

and their F# equivalents:

let map f xs = seq {
    for x in xs do 
        yield f x 
    }

let reduce f init items =
    let mutable current = init
    for item in items do
        current <- f current item
    current

Brian's post is a good overview of how F# type inference works. He illustrates how type inference in F# gives the language an edge over C#:

Though type inference is “just” syntax sugar, it really can matter; there are cases where you’d never write cool functional programming code in C# because you get completely swamped under by the type annotations. As an example see here; one of the C# functions in that example is this monstrosity:

static Tree<KeyValuePair<A, bool>> DiffTree<A>(Tree<A> tree, Tree<A> tree2)
{
    return XFoldTree((A x, Func<Tree<A>, Tree<KeyValuePair<A, bool>>> l, Func<Tree<A>,
      Tree<KeyValuePair<A, bool>>> r,  Tree<A> t) => (Tree<A> t2) =>
        Node(new KeyValuePair<A, bool>(t2.Data, object.ReferenceEquals(t, t2)),
             l(t2.Left), r(t2.Right)),
        x => y => null, tree)(tree2);
}

and yes, every single one of those type annotations is required by C# 4.0. Here’s the corresponding F# code that uses the same identifier names:

let DiffTree(tree,tree2) =
    XFoldTree (fun x l r t t2 ->
        let (Node(x2,l2,r2)) = t2
        Node((x2,t===t2), l l2, r r2)) (fun _ _ -> Leaf) tree tree2

I've had discussions relating to the use of var in C# where people say that you need the type annotations to be able to understand code when reading it but I'm not convinced. With type inference it seems like you're seeing the code at a higher level, making it easier to understand without so much clutter from implementation details, but I haven't worked on a large scale project using a language with type inference so I can't really say for sure one way or the other.