Functional C# – Forward Functional Composition

In the last post, we talked about partial application and currying with respect to functional composition.  I showed the power of functional composition in regards to a real-world example of how to calculate a book price given the chain of potential discounts, taxes, shipping, etc.  Through functional composition, we are able to add additional calculations with relative ease.  In today’s example, let’s revisit some of those topics and explore some areas I haven’t touched yet.

Revisiting Currying

Before we get going, I wanted to revisit currying because I’m not sure that people fully understand the difference between the currying and partial application.  As you may recall, currying is a way of accomplishing partial application through taking a function with multiple arguments and returning a new function which it can be called as a chain of functions with only one argument each.  To make this a little more concrete, let’s take the trite add function, but let’s add one more parameter to it.  This example should show that we are indeed breaking down a multi-parameter function into one that expects only one parameter at a time.

public static class FuncExtensions
{
    public static Func<TArg1, Func<TArg2, Func<TArg3, TResult>>> Curry<TArg1, TArg2, TArg3, TResult>(
        this Func<TArg1, TArg2, TArg3, TResult> func)
    {
        return arg1 => arg2 => arg3 => func(arg1, arg2, arg3);
    }
}

class Program
{
    static void Main(string[] args)
    {
        // Currying 3 parameter function
        Func<int, int, int, int> add = (x, y, z) => x + y + z;
        var curriedAdd = add.Curry();
        
        // Apply one parameter at a time
        var curriedResult = curriedAdd(3)(4)(5);
        Console.WriteLine(curriedResult);
    }
}

Note the signature of our Curry extension method and you will notice that each time, we create a function which takes a single argument and then returns a function which takes the next parameter and if the last one, will return the result.  If we take a look at partial application instead for this function, this might be applying a single argument, and then afterwards, applying the final two arguments. 

public static class FuncExtensions
{
    public static Func<TArg2, TArg3, TResult> Apply<TArg1, TArg2, TArg3, TResult>(
        this Func<TArg1, TArg2, TArg3, TResult> func, TArg1 arg1)
    {
        return (arg2, arg3) => func(arg1, arg2, arg3);
    }
}

class Program
{
    static void Main(string[] args)
    {
        Func<int, int, int, int> add = (x, y, z) => x + y + z;
        
        // Partially apply only first argument
        var partialAdd = add.Apply(3);
        
        // Then apply second and third
        var partialResult = partialAdd(4, 5);
        Console.WriteLine(partialResult);
    }
}

The Apply function above should give the clue that we return a function that takes the last two arguments and returns our final result.  This way we can supply the argument 3 to our function, and later we can apply the 4 and the 5 to complete the function call to return the result.  We could make this a little more real by taking a function such as the fold and both curry and partial apply to see the side-by-side differences.

Func<int, Func<int, int, int>, IEnumerable<int>, int> fold = (s, f, i) => i.Aggregate(s, f);

// Curried solution
var curriedFold = fold.Curry();
var curriedOneSeedFold = curriedFold(1);
var curriedFactorial = curriedOneSeedFold((acc, x) => acc * x);
Console.WriteLine(curriedFactorial(Enumerable.Range(1, 10)));

// Partially applied solution
var appliedFactorial = fold.Apply(1, (acc, x) => acc * x);
Console.WriteLine(appliedFactorial(Enumerable.Range(1, 10)));

Now that it should be a little bit more apparent the differences between the two, at least using the verbose C# syntax required to pull these things off.  Let’s move onto another topics of functional composition.

Forward Partial Application and Composition

Both forward application and composition is quite important in the functional programming world.  First, let’s tackle the forward application which allows us to specify the final argument first to a function.  In F#, we have the |> operator which allows us to do this.  Let’s take a look at a simple example of using this:

// val (|>) :: 'a -> ('a -> 'b) -> 'b
let mapped = [1..10] |> List.map (fun x -> x * x)

What this allows us to do is have the partially applied List.map function which takes two arguments, the function and the list, and then forward the final argument, the list, to it.  In C# terms, how could we pull this off?

public static class FuncExtensions
{
    public static Func<TArg2, TResult> Apply<TArg1, TArg2, TResult>(
        this Func<TArg1, TArg2, TResult> func, TArg1 arg1)
    {
        return arg2 => func(arg1, arg2);
    }
    
    public static TResult Forward<TSource, TResult>(
        this TSource source, Func<TSource, TResult> func)
    {
       return func(source);
    }    
}

class Program
{
    static void Main(string[] args)
    {
        Func<Func<int, int>, IEnumerable<int>, IEnumerable<int>> map = 
            (f, i) => i.Select(f);
        var mapped = Enumerable.Range(1, 10).Forward(map.Apply(x => x * x));
    }
}

As you can see, it’s a little verbose, but can be done.  We first need the forward function to allow us to specify the last argument first.  As the map function takes two arguments, we need to partially apply the squaring function to the map to then create a function which takes one more argument.  Next, we can compose partially applied functions together rather easily.  In this case, we pass in our initial list and then cube each number through a map, then the results are then filtered to check for a mod 3, and then finally take that result and multiply the accumulator by each number in the list.

let result =  
  [1..10] 
    |> List.map (fun x -> x * x * x) 
    |> List.filter (fun x -> x % 3 = 0)
    |> List.fold_left (fun acc x -> acc * x) 1  

In C#, we can do the very same such as the following:

Func<Func<int, int>, IEnumerable<int>, IEnumerable<int>> map = (f, i) => i.Select(f);
Func<Func<int, bool>, IEnumerable<int>, IEnumerable<int>> filter = (f, i) => i.Where(f);
Func<int, Func<int, int, int>, IEnumerable<int>, int> fold = (s, f, i) => i.Aggregate(s, f);

var res = Enumerable.Range(1, 10)
    .Forward(map.Apply(x => x * x * x))
    .Forward(filter.Apply(x => x % 3 == 0))
    .Forward(fold.Apply(1, (acc, x) => acc * x));

But, what about functional composition?  How can we not specify the collection beforehand, yet tie these functions together?  The answer is rather simple.  In F#, we might be able to do something like the following using the >> operator:

// (>>) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c
let mapFilterReduce =
  List.map (fun x -> x * x * x)
    >> List.filter (fun x -> x % 3 = 0)
    >> List.fold_left (fun acc x -> acc * x) 1 

This allows us to compose our functions together in such a way that it reads from left to right, so that we first map, then filter, then fold.  Using C#, we can use some of the functions we’ve already defined to do the same thing such as the following:

public static class FuncExtensions
{
    public static Func<TSource, TResult> ForwardCompose<TSource, TIntermediate, TResult>(
        this Func<TSource, TIntermediate> func1, Func<TIntermediate, TResult> func2)
    {
        return source => func2(func1(source));
    }
}

Func<Func<int, int>, IEnumerable<int>, IEnumerable<int>> map = (f, i) => i.Select(f);
Func<Func<int, bool>, IEnumerable<int>, IEnumerable<int>> filter = (f, i) => i.Where(f);
Func<int, Func<int, int, int>, IEnumerable<int>, int> fold = (s, f, i) => i.Aggregate(s, f);

// Compose together
var mapFilterFold = map.Apply(x => x * x * x)
    .ForwardCompose(filter.Apply(x => x % 3 == 0))
    .ForwardCompose(fold.Apply(1, (acc, x) => acc * x));
Console.WriteLine(mapFilterFold(Enumerable.Range(1, 10)));

But, what about reversing them?  Well, that’s for next time…

Conclusion

The ideas of functional composition is quite powerful in that we can chain our functions together to create more powerful functions to solve difficult problems and help model some more complex algorithms.  Although there is some syntactic overhead to using C# as it doesn’t support these constructs natively, with a little effort, we can also have this functionality.  At this point, you may wonder why we’d try and not use F#, which is a very valid question.  In the next post in this series, we’ll cover composition from right to left and see how that can be done using C# as well.

This entry was posted in C#, F#, Functional Programming. Bookmark the permalink. Follow any comments here with the RSS feed for this post.