4.12.2.1 - Higher-order functions, map, filter and fold (C#)

Higher-order functional programs

A higher-order function accepts another function as an argument, returns a function as its result, or does both.

Functions can describe transformations without repeatedly changing shared state. A pure function gives the same result for the same arguments and has no observable side effects, such as changing its input list or a global counter. An expression returning a new list can be pure even if its implementation uses temporary local variables. C# supports this style alongside imperative and object-oriented programming; C# syntax alone does not make a function pure.

using System;

class Program
{
    static int Twice(Func<int, int> transform, int value)
    {
        return transform(transform(value));
    }

    static Func<int, int> MakeIncrease(int amount)
    {
        return value => value + amount;
    }

    static void Main()
    {
        Func<int, int> increaseTwo = MakeIncrease(2);
        Console.WriteLine(Twice(increaseTwo, 5)); // 9
    }
}

Twice accepts a function, while MakeIncrease returns one. The inner transformation changes 5 to 7; the outer one changes 7 to 9. Neither changes the stored value 5. increaseTwo itself accepts and returns integers, so it is not higher-order. Passing an operation as data allows the same control pattern to use a different transformation without rewriting that pattern.

Map transforms each element

Map applies a supplied function to every element and returns the results in corresponding order.

For a function $f:A\to B$, map transforms a list of $A$ values into a list of $B$ values. For example, applying $f(x)=3x$ to $[2,4,1]$ gives $[6,12,3]$. The result has the same length as the input, including an empty result for an empty input. Duplicate inputs produce duplicate mapped results. The result type may change: mapping string length over $[\text{“red”},\text{“blue”}]$ gives $[3,4]$.

C# LINQ's Select implements this operation. using System.Linq; makes the extension method available, and ToList() evaluates the resulting sequence and collects it into a new list.

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

class Program
{
    static void Main()
    {
        List<int> readings = new List<int> { 2, 4, 1 };
        Func<int, int> triple = value => 3 * value;
        List<int> scaled = readings.Select(triple).ToList();
        Console.WriteLine(string.Join(", ", scaled)); // 6, 12, 3
        Console.WriteLine(string.Join(", ", readings)); // 2, 4, 1
    }
}

Select receives the function value triple, not triple(2). The transformation is applied once for each input element when this sequence is materialised. LINQ normally uses deferred evaluation for Select and Where; without ToList(), their results describe sequences to evaluate later. Here the input is unchanged and each result is stored separately. C# lists themselves remain mutable, so preserving them is a deliberate choice in this program.

Filter selects matching elements

Filter keeps exactly the original elements that satisfy a supplied condition, preserving their order.