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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s