Functional C# – Reverse Functional Composition

In the previous post, I covered currying as well as left to right functional composition.  I showed that with a few extensions methods to our functions, we can create rich, albeit verbose, solutions through functional composition.  But, what about going from right to left in functional composition?  Could that be done as well?

Before we move on, let’s get caught up to where we are today:

Going From Right to Left

Since we covered in the last post on using left to right functional composition, I thought it was only fair to cover going from right to left.  In Haskell, we have a built-in ( . ) operator to the Prelude which looks something like the following:

*Main> :t ( . )
(.) :: (b -> c) -> (a -> b) -> a -> c

This allows us to compose from right to left in a pretty easy manner.  For example, we can take the function we had in the previous post that goes from left to right and convert it:

*Main> let mapFilterFold = foldl (*) 1 . filter ((==) 0 . flip mod 3) . map (flip (^) 3)
*Main> :t mapFilterFold
mapFilterFold :: [Integer] -> Integer
*Main> mapFilterFold [1..10]
4251528

First, we are cubing all numbers by flipping the power operator so that we can partially apply the mapped item later.  Next, we flip the order of the modulo operator so that we can partially apply the filtered item later, and then we compose it to check that it equals 0.  Finally, we fold the result with the multiply operator with a seed of 1.  Similarly, using F# we can accomplish the same task using the (<<) operator.

> let flip f x y = f y x
-
- let mapFilterFold =
-   List.fold_left (*) 1
-     << List.filter ((=) 0 << flip (%) 2)
-     << List.map (flip pown 3);;

val flip : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c
val mapFilterFold : (int list -> int)

> mapFilterFold [1..10];;
val it : int = 4251528

Simple yet elegant solutions to the issue at hand.  You can see the beauty of functional composition in the place on anonymous functions, to reuse ones we’ve already defined or have been defined for us.  But, what about C#?  What can be done there?

public static class FuncExtensions
{
    public static Func<TSource, TResult> ReverseCompose<TSource, TIntermediate, TResult>(
        this Func<TIntermediate, TResult> func2, Func<TSource, TIntermediate> func1)
    {
        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);

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

We can verify the behavior with the other implementations as we have above that we have the exact same answer.  We can now chain these functions together in reverse to get the same answer as chaining them together in a left to right manner.  I could use Pex to verify this behavior with parameterized tests which would be my choice for these kinds of tests.  We’ll get into the full details of these tests later, but here might be an example of verify this behavior.

[PexMethod]
public void Forward_Should_Equal_Reverse([PexAssumeNotNull] int[] numbers)
{
    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 mapFilterFold1 = map.Apply(x => x * x * x)
        .ForwardCompose(filter.Apply(x => x % 3 == 0))
        .ForwardCompose(fold.Apply(1, (acc, x) => acc * x));
    var result1 = mapFilterFold1(numbers);

    var mapFilterFold2 = fold.Apply(1, (acc, x) => acc * x)
        .ReverseCompose(filter.Apply(x => x % 3 == 0))
        .ReverseCompose(map.Apply(x => x * x * x));
    var result2 = mapFilterFold2(numbers);

    Assert.Equal(result1, result2);
}

The Application Operator

But, there’s one operator we haven’t talked about, the Application ( <| ) operator.  This allows us specify things in the exact order as they are, but, the power it gives us is that we can now leave out parentheses.  Take the following code as an example:

// val (<|) : ('a -> 'b) -> 'a -> 'b
module Map =
  let containsKey (k:'k) (m:Map<'k,'a>) =
    m.ContainsKey k
    
  let notContainsKey (k:'k) (m:Map<'k,'a>) =
    not <| containsKey k m

Normally, we’d have to put a set of parentheses around the containsKey k m inside the notContainsKey, but instead through this operator, we rid ourselves of that need.  Any time I can reduce the need for them the better as they tend to clutter up my function definitions. 

In Haskell, we have the same capability as well through the use of the ( $ ) application operator.  Let’s look at defining the notContainsKey construct as we did for F#, realizing of course member and notMember already exist.

*Main> :m + Data.Map
*Main Data.Map> :t ($)
($) :: (a -> b) -> a -> b
*Main Data.Map> let notMember' k m = not $ member k m
*Main Data.Map> :t notMember'
notMember' :: (Ord k) => k -> Map k a -> Bool

Likewise as we had with F#, we can omit those pesky parentheses to achieve cleaner code.  But, does it make any sense for C#?  The answer is, yes, we can achieve it, but for what purpose?  If our purpose for this operator is to lose the parentheses, there is nothing we can do in C# to change that, so I don’t really see the point.

Conclusion

I hope you enjoyed this little foray back into Functional C# code as I talked about functional composition, currying and partial application.  The ideas expressed in this series are to help maximize code reuse and allow for flexible applications.  Using C#, we are able to express a lot of the functional constructs we take for granted in languages such as Haskell and F#.  And we also see where C# doesn’t quite match up to the other functional languages, especially around the application operator.   I hope to in the near future update my Functional C# library on MSDN Code Gallery to reflect some of these further thoughts I’ve had since I last updated.

No Comments