warning: Creating default object from empty value in /home3/ideaquar/public_html/hugoestrada/modules/taxonomy/ on line 33.

Haskell, C#: map, filter, and fold in C# via linq

Looping is a fundamental concept in computer programming. And to most programmers familiar with imperative c-syntax languages, it looks something like this:

  foreach (var s in stringList)

The idiom is simple: we are going to go through each item in the list, and we will process that element in some manner. In most cases, we are either transforming each element, we are filtering the elements, or we are carrying out some sort of accumulation. To know which of these actions is being carried out we would have to read carefully what is happening in between the curly brackets.

So, looking at the code, we instantly know that we are doing something with every element. But at a glance we don\'t know what that something is.

Functional programming gives us three (3) functions to loop through lists. These are map(), filter(), and fold(). The final result between imperative looping and the functional functions is the same, but we gain semantic clues with the functional functions to what the looping id doing.

C# is a remarkable language. Although it was born as an imperative language, it has been supporting more and more functional operations through linq. Below I will briefly describe the three looping functions, and then I will show its imperative equivalent, followed by its equivalent in using linq.

map() will take a function followed by a list. Each element in the list will be transformed by the function, and the output will be a list of transformed values. In haskell it looks like this

x = map (* 5) [3,4,5,6,3]

Translated into imperative C# code it looks like this:

var result = new List<int>();
var list = new list<int> { 3,4,5,6,3};
foreach (var n in list)
  result.Add(5 * n);

In linq, to express the above function, we us the select query thingy and write

  var query_result = (from n in new List<int> { 1, 2, 3, 4, 5 }
                           select n * 5).ToList();

Sometimes we use loops to filter values out. Functional programming languages have filter(), which takes a predicate function, one with a condition, and a list, and returns a list that meets the filter condition.

x = filter (> 5) [3,4,5,6,3]

Its procedural code in C#:

var result = new List<int>();
var list = new list<int> { 3,4,5,6,3};
foreach (var n in list)
  if (n > 5)
    result.Add( n);

And its functional version in C# via linq. For filter, we mainly use the where clause in a linq query.

   var query_result = (from n in new List<int>() { 1, 2, 3, 4, 5 }
                                  where n > 5
                                  select n).ToList();

The final looping case that I will show is aggregating a value, such as a total from all of the numbers in a list. This operation is called fold in functional programming, since the person naming the function imagined a paper list of values being folded one at a time. foldl takes a function, a list, and an initial value.

x = foldl (+) 0 [3,4,5,6,3]

This is equivalent to procedural C# to

var result = 0;
var list = new list<int>{ 3,4,5,6,3};
foreach (var n in list)
   result += n;

In functional C# via linq we write:

  var query_result = (from n in new List<int>{ 1, 2, 3, 4, 5 }
                                select n).Sum() ;

The above was shown to keep the parallelism between the examples. In actual use, one would most likely use a IEnumerable extension method in the following form:

  var result =  new List<int> { 1, 2, 3, 4, 5 }.Sum();

As we have seen, the functional methods map, filter, and fold have an semantic advantage over procedural looping in that they clearly tell you what the looping is doing. C# has the capabilities of doing functional statements. Although not giving the same terse syntax or its immediate semantic meaning, the linq functional-like methods approximate functional terseness and reduces, although not eliminates, the semantic ambiguity the semantic ambiguity that procedural loops have.

Syndicate content