Tuesday, June 10, 2014

C# and a Functional Style

One weekend I dove headfirst into Haskell via "Learn you a Haskell for Great Good" for nothing more than something to learn... and walked away very discouraged with most of the code I wrote up to that point...  The following Monday, I went to work, and noticed the code that I previously found elegant, felt crude.  In particular, large methods that used and manipulated multiple members from the class.  Unfortunately, I didn't have the option to move from C# to Haskell or even F#... So I just remained dissatisfied.

Not all was lost however, over the next few days I noticed there was hope... C# actually had many elements that allow functional styles.  In particular:


  • Lazy Evaluation and Infinite Sequences
  • Function Chaining
  • Lambda Statements
  • Higher Order Functions

Lazy Evaluation and Infinite Sequences


While C# is not totally lazy, it does have a lazy feature via the keyword yield.  A function that uses yield is lazy.  It will not be called until the results are requested.  Lets look at an example:


/// <summary>
/// A lazy function that returns an infinite sequence of integers.
/// </summary>
/// <param name="start">The value to start at.</param>
/// <param name="incBy">The value increments by.</param>
/// <returns>An infinite sequence.</returns>
public static IEnumerable<int> Range(int start = 0, int incBy = 1)
{
  for (int i = start; true; i += incBy)
    yield return i;
}

static void Main(string[] args)
{
  // This code never accesses any values.
  var x = Range();
}


If you ran this in debug mode, and placed a breakpoint in the function Range(), you would notice that the function is never called.  This is because we never request any values from the infinite sequence.

Function Chaining

With the addition of LINQ, my code has often turned into several series of data structure transformations.  With functional programming, this is very natural, however in C# it would normally look something like the following:

A(B(C(D(9))))

Where A, B, C, and D are all methods.  I personally don't find this very elegant or even readable.  However, the .NET team provided a solution through extension methods.  Lets look at some actual code:


static class Program
  {

    /// <summary>
    /// This will adjust all the case of the lines to lower.
    /// </summary>
    /// <returns>A sequence of lower case lines.</returns>
    public static IEnumerable<String> AdjustLines(IEnumerable<String> lines)
    {
      return lines.Select(line => line.ToLower());
    }

    /// <summary>
    /// This takes two sequences and pairs each value together as a Tuple.
    /// </summary>
    /// <returns>A sequence of Tuples.</returns>
    public static IEnumerable<Tuple<T1, T2, T3>> Zip<T1, T2, T3>(
        this IEnumerable<T1> a, IEnumerable<T2> b, IEnumerable<T3> c)
    {
      var ea = a.GetEnumerator();
      var eb = b.GetEnumerator();
      var ec = c.GetEnumerator();
      while (ea.MoveNext() & eb.MoveNext()& ec.MoveNext())
        yield return Tuple.Create(ea.Current, eb.Current, ec.Current);
    }

    /// <summary>
    /// Compare each line and return only the ones that differ.
    /// </summary>
    /// <param name="values">A zipped up sequence of 2 lines and a line number.</param>
    /// <returns>Returns a sequence of differing lines.</returns>
    public static IEnumerable<Tuple<String, String, Int32>> CompareLines(
        this IEnumerable<Tuple<String, String, Int32>> values)
    {
      return values.Where(t => t.Item1 != t.Item2);
    }

    /// <summary>
    /// Verify if a number is prime.
    /// </summary>
    /// <returns>Returns true if the number is prime and false otherwise.</returns>
    public static bool IsPrime(int number)
    {
      for (int i = 2; i < (int)Math.Ceiling(Math.Sqrt(number)); i++)
        if (number % i == 0)
          return false;

      return true;
    }

    /// <summary>
    /// Filter out the differing lines for only the ones that happen to have prime line numbers.
    /// </summary>
    /// <returns>A sequence of lines that have prime line numbers.</returns>
    public static IEnumerable<Tuple<String, String, Int32>> FilterForPrimeLines(
        this IEnumerable<Tuple<String, String, Int32>> values)
    {
      return values.Where(t => IsPrime(t.Item3));
    }

    /// <summary>
    /// A lazy function that returns an infinite sequence of integers.
    /// </summary>
    /// <param name="start">The value to start at.</param>
    /// <param name="incBy">The value increments by.</param>
    /// <returns>An infinite sequence.</returns>
    public static IEnumerable<int> Range(int start = 0, int incBy = 1)
    {
      for (int i = start; true; i += incBy)
        yield return i;
    }

    /// <summary>
    /// Prints the results of everything.
    /// </summary>
    public static void PrintResults(this IEnumerable<Tuple<String, String, Int32>> results)
    {
      foreach (var r in results)
        Console.WriteLine(String.Format("#{0} -> [A]{1} != [B]{2}", r.Item3, r.Item1, r.Item2));
    }

    static void Main(string[] args)
    {
      var a = File.ReadLines(@"C:\temp\a.txt");
      var b = File.ReadLines(@"C:\temp\b.txt");

      // Normal style
      PrintResults(FilterForPrimeLines(CompareLines(Zip(a, b, Range()))));

      // Functional/Pipeline style
      a.Zip(b, Range())
        .CompareLines()
        .FilterForPrimeLines()
        .PrintResults();
    }

The most vital section of code to view is the "main()" function.  There we have the two different styles in discussion.  First we have the normal way, where each function calls the next in a traditional way. At the end of the statement we end up with 5 ')'s... It doesn't read well and is difficult to follow.

However, after that we have the "new" way, where we take advantage of extension methods and chain them together.  This offers a far cleaner and more readable statement.  (It also integrates better with any LINQ functionality you may use.)

Lambda Statements

Lambda statements are well documented all over the internet, but are still worth mentioning.  Lambda statements are HEAVILY used in functional programming and offer developers the option to make and pass very simple to very complex functions on the fly.  If you have ever used LINQ, then you have used them...

Higher Order Functions

Higher order functions (currying and partial functions) are now possible due to lambda statements.   Jon Skeet has an excellent post worth checking out on currying vs partial functions.  I don't plan to repeat his work, as I don't think I can do a better job...

Summary

Functional programming is possible (though not required) in C#.  Programming in such a style can offer several benefits and is worth considering.  At the very least, it can help a developer to think differently and approach an algorithm from a different light.