.NET, F#, Programming

Sequences and problem solving in F#

Sequences in F# is very similar to the lists: they represent ordered collection of values. However, unlike lists, sequences are lazy evaluated, meaning elements in a sequence computed as they needed. This is very handy for example to represent infinite data structures. Data types, such as lists, arrays, sets, and maps are implicitly sequences because they are enumerable collections. A function that takes a sequence as an argument works with any of the common F# data types, in addition to any .NET data type that implements System.Collections.Generic.IEnumerable<'T>. The type seq<'T> is a type abbreviation for IEnumerable<'T>. This means that any type that implements the generic System.Collections.Generic.IEnumerable<'T>, which includes arrays, lists, sets, and maps in F#, and also most .NET collection types, is compatible with the seq type and can be used wherever a sequence is expected. Sequences contains over than 70 operations which I will not list here. You can follow refences Sequences and F# – Sequences for more details.

In this post I would like to look at the real world example in practice and compare both: C# and F# approaches to solve the same problem. Lets describe it:

Print all working (business) days within specified date range.

To make it more interesting, we would like to support an interval: when specified we return values for each n working day instead of each day.

First, lets look at one of the possible C# implementations:

using System;
using System.Linq;
using System.Collections.Generic;

public class Program {

 public static void Main() {

  var startDate = new DateTime(2020, 06, 01);
  var endDate = new DateTime(2020, 07, 01);
  var interval = 2;
  Func<DateTime, bool> IsWorkingDay = (date) => 
        date.DayOfWeek != DayOfWeek.Saturday && date.DayOfWeek != DayOfWeek.Sunday;

  foreach(var date in GetWorkingDays(startDate, endDate, IsWorkingDay)
                      .Where((d, i) => i % interval == 0)) 
  {
      Console.WriteLine(date);
  }
 }

 private static IEnumerable<string> GetWorkingDays(DateTime start, DateTime stop, Func<DateTime, bool> filter) {

  var date = start.AddDays(-1);

  while (date < stop) {
   date = date.AddDays(1);

   if (filter(date)) {
    yield return string.Format("{0:dd-MM-yy dddd}", date);
   }
  }
 }
}

The code is pretty straightforward: we use IEnumerable<string> to generate a sequence of values which is filtered by business days. Note that enumerable is lazy evaluated. Then we apply LINQ extension:

Where<TSource>(IEnumerable<TSource>, Func<TSource,Int32,Boolean>)

which takes an integer as a second parameter. It selects only values where index is divisible by interval without remainder, hence satisfying requirement of getting each n business days.

Finally, with interval of 2 we will have output similar to this:

01-06-20 Monday
03-06-20 Wednesday
05-06-20 Friday
09-06-20 Tuesday
11-06-20 Thursday
15-06-20 Monday
17-06-20 Wednesday
19-06-20 Friday
23-06-20 Tuesday
25-06-20 Thursday
29-06-20 Monday
01-07-20 Wednesday

Next, I will show you F# implementation.

In F#, generally, solving any problem implies decomposition on granular level of a function and composing these functions in specific order and with a glue in a form of a language constructs.

First, lets define a working day filter:

let IsWorkingDay (day : DateTime) = day.DayOfWeek <> DayOfWeek.Saturday && day.DayOfWeek <> DayOfWeek.Sunday

Now, lets define an infinite sequence of a days following some start date:

let DaysFollowing (start : DateTime) = Seq.initInfinite (fun d -> start.AddDays(float (d)))

Next, we need a function to represent a sequence of working days starting from some start date which is essence a composition of DaysFollowing function with IsWorkingDay filter with a help of a pipeline operator:

let WorkingDaysFollowing start = 
   start
   |> DaysFollowing
   |> Seq.filter IsWorkingDay

Notice the use of Seq.filter operation here. We just provide filtering function with following signature:

where : ('T → bool) → seq<'T> → seq<'T>

This should be familiar to you if you ever used LINQ 🙂 In F#, 'T notation just means generic type.

At this point we would like to have a function which could make use of an interval variable in generation of the next working date. Here it is:

let NextWorkingDayAfter interval start = 
   start
   |> WorkingDaysFollowing
   |> Seq.item interval

And again, we stack one block on top of another which is function composition in action. Seq.item computes the nth element in the collection. First, we get sequence of working days and then we process nth from that sequence:

item : int → seq<'T> → 'T

Finally, we need to define function which will compose all these blocks and return final sequence of dates. We want our resulting sequence to be a string representation of a working dates according to original requirement. That’s how we could achieve that:

let WorkingDays startDate endDate interval = 
   Seq.unfold (fun date -> 
      if date > endDate then None
      else 
         let next = date |> NextWorkingDayAfter interval
         let dateString = date.ToString("dd-MMM-yy dddd")
         Some(dateString, next)) startDate

We use unfold function here. It is one of the most complex operations in Seq data type to understand, yet very powerful. There is no direct analogy of it in C#. Put it simple: function returns a sequence that contains the elements generated by the given computation. The signature of that function is:

unfold : ('State → 'T * 'State option) → 'State → seq<'T>

Lets take a closer look at the unfold function. The first parameter is a computation function which takes the current state and transforms it to produce each subsequent element in the sequence. For the first iteration, the value passed in is the initial state parameter, which is the second parameter passed to the unfold function which is start date in the example above. The computation function (or generator) must return an option type of a two element tuple. The first element of the tuple is the item to be yielded and the second element is the state to pass on the generator function in the next iteration. It returns Some when there are results or None when there are no more results. In our case when passed state (date) is less than end date we calculate next working date (taking in consideration interval) and converting it to string. We wrap it in an option tuple where the first value will be added to resulting sequence and the second value is a state which will be passed to next iteration of the unfold.

We invoke it as follows:

WorkingDays (DateTime(2020, 6, 1)) (DateTime(2020, 7, 01)) 2 |> Seq.iter (fun x -> printfn "%s" x)

Which produce the same output as C# version

Put it all together:

open System

let IsWorkingDay (day : DateTime) = day.DayOfWeek <> DayOfWeek.Saturday && day.DayOfWeek <> DayOfWeek.Sunday
let DaysFollowing (start : DateTime) = Seq.initInfinite (fun i -> start.AddDays(float (i)))

let WorkingDaysFollowing start = 
   start
   |> DaysFollowing
   |> Seq.filter IsWorkingDay

let NextWorkingDayAfter interval start = 
   start
   |> WorkingDaysFollowing
   |> Seq.item interval

let WorkingDays startDate endDate interval = 
   Seq.unfold (fun date -> 
      if date > endDate then None
      else 
         let next = date |> NextWorkingDayAfter interval
         let dateString = date.ToString("dd-MMM-yy dddd")
         Some(dateString, next)) startDate

Conclusion

In F# function composition plays an important role. You start by splitting complex problem in smallest possible pieces and wrapping it into the functions. This is what known as decomposition. To solve a problem you need to compose these functions in certain way. Very much like LEGO bricks. Side effect which gives you such granular decomposition is re-usability: once defined, function can be applied in different contexts and to make it fit functional languages provides rich set of tools which is out of scope of the article. On the other hand, C# and OOP in general gives you classes and design patterns to solve same problems, often in a much more verbose and error-prone way.

.NET, C#, Programming

Make your C# code cleaner with functional approach

Since introducing LINQ in .NET 3.5, the way how we write code changed a lot. Not only in the context of database queries with LINQ to SQL or LINQ to Entities, but also in day-to-day work with manipulating collections and all kind of transformations. Powerful language constructs like implicitly typed variables, anonymous types, lambda expressions and object initializers, gave us tools for writing more robust and conciseness code.

It was a big step towards functional approach to solve engineering tasks by using a more declarative way of expressing your intent instead of sequential statements in imperative paradigm.

Functional programming is a huge topic and mind shift for all .NET developers who is writing their code in C# for a long time. If you are new to the topic (like me), you probably don’t want to get into all that scary sounding things like functors, applicatives or monands right now (discussion for other posts). So let’s see how applying a functional approach could make your code cleaner here and now with our beloved C#.

For the sake of example we will solve a very simple FizzBuzz kata in C#. I will show you how it looks like in F#. If you don’t know what is kata, it just a fancy way of saying puzzle or coding task. The word kata came to us from the world of martial arts and particularly Karate. The FizzBuzz is a simple coding task where you need to solve the following problem:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz “

So, first we will start with naïve implementation in C#:

void Main()
{
    for(var i = 1; i <= 100; i++)
    {
        if(i % (3 * 5) == 0)
            Console.WriteLine("FizzBuzz");
        else if(i % 3 == 0)
            Console.WriteLine("Fizz");
        else if(i % 5 == 0)
            Console.WriteLine("Buzz");
        else
            Console.WriteLine(i);
    }   
}

And here’s the output:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
...

So far so good. I told you, it’s a piece of a cake. Okay, how we can improve this code? Let’s use the power and beauty of LINQ:

void Main()
{
	var result = Enumerable
		.Range(1, 100)
		.Select(x => {
			switch(x)
			{
				case var n when n % (3 * 5) == 0: return "FizzBuzz";
				case var n when n % 3 == 0: return "Fizz";
				case var n when n % 5 == 0: return "Buzz";
				default: return x.ToString();
			}			
		})
		.Aggregate((x, y) => x + Environment.NewLine + y);
	
	Console.WriteLine(result);
}

We use the static helper Range on Enumerable to generate a sequence from 1 to 100. Then we use the Select method to iterate over each number in that range and return a string which contains one of those FizzBuzz words. We used very powerful concept – pattern matching. This feature is available from C# 7.0. This variation of pattern matching uses var pattern with when clause for specifying condition. Last method in chain is Aggregate. It is one of the most interesting in the LINQ – you could use it as a functional replacement for the loops in your code base. In this example we concatenated each element in sequence with a new line producing string as a result.

In C# 8.0 pattern matching was extended and improved. We can re-write our code like this:

public static string FizzBuzz(int n) =>
        (n % 3, n % 5) switch
        {
            (0, 0) => "FizzBuzz",
            (0, _) => "Fizz",
            (_, 0) => "Buzz",
            (_, _) => $"{n}"
        };
 
 static void Main(string[] args)
 { 
     foreach (var n in Enumerable.Range(1, 100))
     {
         Console.WriteLine(FizzBuzz(n));
     }
 }

This syntax is much closer to how pattern matching is applied in functional languages. In functional languages _ is called a discard symbol – meaning we are not interested in value in that position. We used what is called tuple pattern here.

  • When remainder of 3 and 5 in both positions 0 – we print “FizzBuzz”.
  • When remainder of 3 is 0 and we not interested in the remainder of 5, we print “Fizz”.
  • When the remainder of 5 is 0 and we not interested in the remainder of 3 we print “Buzz”.
  • For all other cases we just print value of the n.

Remember, in pattern matching order matters – first matched condition win and further calculation stops.

Finally, let’s look at the F# implementation of the kata:

let fizzBuzz list  = 
    list |> List.map (fun x -> 
        match (x % 3, x % 5) with
        | (0, 0) -> "FizzBuzz"
        | (0, _) -> "Fizz"
        | (_, 0) -> "Buzz"
        | _ -> string x
    )

fizzBuzz [1..100] |> List.iter (fun x -> printfn "%s" x)

You can see that this sample is very similar to the previous one with C# 8.0 pattern matching. And this should not surprise you, because the C# team is introducing more and more functional constructs in the language with each version, taking all the good parts from F#.