Functional C# - Unfolding Lists
But, that's not to stop us from having fun with trying to implement some of the features of the F# libraries in C#. In fact, that helps you gain the understanding of what it may be doing underneath the covers. I find it's easier sometimes to teach the fundamentals of functional programming through the use of C# for those in the imperative and OO mindset. Today, let's walk through a few samples of creating lists through functional programming techniques. But first, a correction.
Corrected on Currying
As I mentioned before, currying is the simple act of reducing a function with multiple arguments into a single argument high order function. I posted the typical example using the Func, but wasn't quite right on the Action one. My thanks to Alexey Romanov for pointing this out.
public static Func<TArg1, Action<TArg2>> Curry<TArg1, TArg2>(this Action<TArg1, TArg2> action)
{
return x1 => x2 => action(x1, x2);
}
Now with both of these currying becomes a bit more natural so that now I can do the following:
Action<IEnumerable<int>, int> contains = (x, y) => x.ShouldContain(y);
var curriedContains = contains.Curry();
var containedBy30 = curriedContains(Enumerable.Range(1, 30));
containedBy30(3);
Still, it's not as natural as I'd like it to be in terms of having to specifically mark is as a curried function instead of it being more natural.
Generating Lists Through Unfolding
This is probably one of the more difficult functions to understand. The goal of the unfold function is to create a delayed evaluation list. What we want is the ability to have a function evaluated repeatedly so that we can generate the items in our list. This evaluation function must return an option type (Option<A>) that can be either Some(x) or None as well as the need for tuples (Tuple<TArg1, TArg2>). But, in C#, we don't have those features. After consulting Dustin Campbell, I noticed that he already has done a bit of legwork in post his post "Apples and Oranges" to compare the performance of a C# and F# solution to a Project Euler problem. Let's look at a sample F# unfolding sample of creating an infinite Fibonacci sequence and then we'll look at how to implement in C#.
let fibs = Seq.unfold (fun (i,j) -> Some(i,(j,i+j))) (1,1)
What we obviously need are the Option<T> and Tuple<TArg1, TArg2> type which Dustin has provided in the download link for the post. I modified mine slightly to follow F# naming conventions for the Tuple to have Item1, Item2 and so on. Now, let's look at the actual implementation of the Unfold function. This function will start with the start value and then calculate the next value from the generator, yield the first item and reset the next item. This will keep on evaluating until the option type returns None which is equivalent to null in the imperative world.
public static IEnumerable<TResult> Unfold<T, TResult>(Func<T, Option<Tuple<TResult, T>>> generator, T start)
{
var next = start;
while (true)
{
var res = generator(next);
if (res.IsNone)
yield break;
yield return res.Value.Item1;
next = res.Value.Item2;
}
}
Now we can define the actual implementation. Let's go ahead and create that implementation using the Unfold function. As you can see, we're pretty much mirroring the F# code snippet word for word. As you may notice, the C# is a bit more verbose because it requires us to physically declare tuples.
var fibs= Unfold(x => Option.Some(Tuple.New(x.Item1, Tuple.New(x.Item2, x.Item1 + x.Item2))), Tuple.New(1, 1));
var first20 = results.Take(20);
Of course I could have done this without the Unfold function and just had a property with an infinite sequence, but I like this solution because it's quite nice and generic. Something like this though could have sufficed:
public static IEnumerable<long> Fibonacci
{
get
{
long i = 1;
long j = 1;
while (true)
{
yield return i;
long temp = i;
i = j;
j = j + temp;
}
}
}
But, then that leaves off the implementing the following section in a nice generic fashion.
Initializing Lists
Now that we understand the unfolding function, we can apply it to any number of operations. How about if we want to initialize a delayed infinite or finite list? We can reuse the logic from the Unfold to make this happen. First, let's look at some F# samples of how we might want to do this:
let allCubes = Seq.init_infinite (fun x -> x * x)
let tenCubes = Seq.init_finite 10 (fun x -> x * x)
The first example, I created a list of all cubes possible, and the second, I created a list of just the first 10. You must create a function which passes in the current iteration, and then you can use it to calculate your return value. Ok, so, how would we do this in C#? Well, let's just first put up the infinite list because it's easier to implement.
public static IEnumerable<T> InitializeInfinite<T>(Func<int, T> f)
{
return Unfold<int, T>(s => Option.Some(Tuple.New(f(s), s + 1)), 0);
}
What I'm doing is return an option type with a tuple of the current value and the next value. Then I seed the function with the starting value of 0. My function that I create is passing in the current index, so that I can increment it. That's pretty easy, but how about limiting it to an exact number of items to take?
public static IEnumerable<T> InitializeFinite<T>(int count, Func<int, T> f)
{
return Unfold<int, T>(s =>
{
if(s < count)
return Option.Some(Tuple.New(f(s), s + 1));
else
return Option<Tuple<T, int>>.None;
}, 0);
}
Now, what I've done is made sure that my index is less than the count specified and then return the next value, or else I return none. With this in place, I can then create the exact duplicates from F# from above:
var allCubes = InitializeInfinite(x => x * x);
var tenCubes = InitializeFinite(10, x => x * x);
Generating Lists
So, in the previous example, we have a way to create a nice list through an initialize function. But what if we want to create a list from some sort of cursor? This cursor could be anything from a stream, to a reader, etc. In F#, we have the generate and generate_using functions which allow us to specify the opening cursor function, the actual computation and then a closing cursor function. Let's look at a quick sample:
let htmlList = Seq.generate (fun () ->
File.OpenText(@"D:\Tools\Reflector\ReadMe.htm")) (fun x ->
if x.EndOfStream then None else Some(x.ReadLine())) (fun x ->
x.Close())
Here I am generating a list of text from a text file, while specifying the opening, calculating of the list, and then the closing. But, since my reader that I'm using supports IDisposable, let's go ahead and use the generate_using, which was created for just that.
let htmlList = Seq.generate_using (fun () ->
File.OpenText(@"D:\Tools\Reflector\ReadMe.htm")) (fun x ->
if x.EndOfStream then None else Some(x.ReadLine()))
There! A bit better. But, how do we do this in C#? Well, let's go ahead and use the Option type that we took from above. From there, we can pretty much go line for line with the F# version. What we want to do is continue executing until we get a None return value and at that point, clean up and then exit.
public static IEnumerable<TResult> Generate<T, TResult>(Func<T> opener, Func<T, Option<TResult>> generator, Action<T> closer)
{
T openerResult = opener();
while (true)
{
var res = generator(openerResult);
if (res.IsNone)
{
closer(openerResult);
yield break;
}
yield return res.Value;
}
}
Now that we have that defined, we can create the GenerateUsing function in much the same way by calling Generate and passing in a function that disposes of the resource.
public static IEnumerable<TResult> GenerateUsing<T, TResult>(Func<T> opener, Func<T, Option<TResult>> generator) where T : IDisposable
{
return Generate(opener, generator, x => x.Dispose());
}
Now, I have the ability to read in files nicely into my lists just by doing this with both the regular generate and generate_using:
var generatedResults = Generate(() => File.OpenText(@"D:\Tools\Reflector\ReadMe.htm"), x =>
{
if (x.EndOfStream)
return Option<string>.None;
else
return Option.Some(x.ReadLine());
}, x => x.Dispose());
generatedResults.ForEach(Console.WriteLine);
var generatedUsingResults = GenerateUsing(() => File.OpenText(@"D:\Tools\Reflector\ReadMe.htm"), x =>
{
if (x.EndOfStream)
return Option<string>.None;
else
return Option.Some(x.ReadLine());
});
generatedUsingResults.ForEach(Console.WriteLine);
The GenerateUsing function is a bit cleaner if we can help it, so that we don't have to worry about a function that closes the resource and instead, we could make a better assumption about the type and close it ourselves generically.
Wrapping It Up
As you can see, you can implement plenty using C# and its current constructs, especially in regards to creating lists. Is it the better approach over F#? No, but it will get you most of the way there as I have shown here with the addition of some more types which include the Tuple<TArg1, TArg2> and the Option<T> type.
The more important thing for you to remember is the bare concepts that this post covered. There are plenty more to learn in terms of recursion (tail, mutual, etc), folding and so on. But, ultimately, I need to get back and focused on my concurrency in F# posts, unless there is a big demand for more of these functional C# samples.
