Converting an IList<T> to an FSharpList<T>

When calling F# functions from other .NET languages, you may encounter situations where you need to pass parameters of type 'T list. F# lists are immutable linked lists, appearing as the type FSharpList<T> in other .NET languages. Hence, passing a typical IList<T> is not possible. Luckily, converting an IList<T> to an FSharpList<T> is easily accomplished by recursively calling FSharpList<T>.Cons, passing each element of the source list. I keep the following code around for those occasions:

public static class Interop
{
	public static FSharpList<T> ToFSharpList<T>(this IList<T> input)
	{
		return CreateFSharpList(input, 0);
	}

	private static FSharpList<T> CreateFSharpList<T>(IList<T> input, int index)
	{
		if(index >= input.Count)
		{
			return FSharpList<T>.Empty;
		}
		else
		{
			return FSharpList<T>.Cons(input[index], CreateFSharpList(input, index + 1));
		}
	}
}

Note how F# lists are terminated using FSharpList<T>.Empty. Using this piece of code is as simple as:

var list = new List<int> { 1, 2, 3, 4 };
var fsharpList = list.ToFSharpList();

Update: @rickasaurus made me aware of the List.ofSeq<'T> function in the F# core library. This function solves the same issue. And, unlike my solution, its implementation is not prone to stack overflows when the input list grows large. In C#, this function is called like this:

var list = new List<int> { 1, 2, 3, 4 };
var fsharpList = ListModule.OfSeq(list);
Advertisements

Tail Recursion in C# and F#

For those of you who are unfamiliar with the notion of tail recursion, let me quote Wikipedia’s definition.

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail call, is a recursive call

Tail recursion is essential in functional languages like F#, where iterative solutions are often implemented using recursion. If the recursion gets too deep, a stack overflow occurs, and your program crashes brutally. The rationale behind tail recursion is that if the recursive call is the last operation of the function, the stack frame of the current function invocation can be discarded before the recursive function invocation is made.

Rather than spending too much time discussing programming theory, let me present two equivalent programs, both containing tail recursion.

C#

class Program
{
	static int n = 1000000;

	static void Countdown()
	{
		if (0 > n--) return;
		Countdown();
	}

	static void Main(string[] args)
	{
		Countdown();
		Console.WriteLine("Done");
	}
}

F#

let n = 1000000

let rec countdown n =
    match n with
    | 0 -> ()
    | _ -> countdown (n-1)

countdown n
printfn "Done"

These two programs are semantically equivalent. They both use tail recursion to count from 1 000 000 to zero, before writing “Done” to the console.

Let us first look at the F# solution. Apart from being precise and easy to comprehend, it actually works. In fact, the F# compiler is smart enough to optimize the countdown function into a simple while loop, producing MSIL equivalent to the following C# code:

public static void countdown(int n)
{
    while (true)
    {
        switch (n)
        {
            case 0:
                return;
        }
        n--;
    }
}

But what about the tail recursive C# solution? While tail recursion optimization has been proposed to Microsoft, the current C# compiler does nothing of the kind. Hence, the resulting MSIL contains a recursive Countdown method. The question is then: “Will the C# solution result in a stack overflow?” Interestingly, the answer is: “It depends.”

It turns out, if you compile the C# code with “Platform target: Any CPU” and run it on a 64-bit version of the Microsoft .NET runtime, the JIT compiler will actually perform tail recursion optimization from the MSIL itself, resulting in a working program. If, however, you compile with “Platform target: x86” or run the program on a 32-bit version of the Microsoft .NET runtime, a stack overflow occurs. This behavior is described in the blog post “Tail call JIT conditions” by David Broman. Basically, the feature sets of the 64-bit and 32-bit versions of the JIT compiler do not coincide.

So, unless you are 100 % certain that your C# application will run on the 64-bit runtime, do no employ tail recursion with the intent of preventing stack overflows. Then again, if you are writing imperative C# code, tail recursion will probably not cross your mind as the best solution to any of your problems.