Functional Programming in C# with LanguageExt

LanguageExt is a library of functional language extensions for C#, created and actively maintained by Paul Louth, and available via the LanguageExt.Core NuGet package.

The implementation of memoization in LanguageExt illustrates several functional concepts. Calling memo on a function memoizes it; i.e., it provides a new function that will cache results for different inputs.

/// <summary>
/// Returns a Func<T,R> that wraps func.  Each time the resulting
/// Func<T,R> is called with a new value, its result is memoized (cached).
/// Subsequent calls use the memoized value.  
/// 
/// Remarks: 
///     Thread-safe and memory-leak safe.  
/// </summary>
public static Func<T, R> memo<T, R>(Func<T, R> func)  
{
    var cache = new WeakDict<T, R>();
    var syncMap = new ConcurrentDictionary<T, object>();

    return inp =>
        matchUnsafe(cache.TryGetValue(inp),
            Some: x => x,
            None: () =>
            {
                R res;
                var sync = syncMap.GetOrAdd(inp, new object());
                lock (sync)
                {
                    res = cache.GetOrAdd(inp, func);
                }
                syncMap.TryRemove(inp, out sync);
                return res;
            });
}
  • Memoization itself is a functional concept: when dealing with pure functions (functions that do not rely on external state, have no side-effects, and always return the same result for the same input) the results can be cached. This caching, called memoization, is normally built in to functional languages; though not natively part of C# it is provided by LanguageExt.
  • The memo function is a static function, so it does not belong to an object which may maintain state.
  • It is a higher-order function a.k.a. functor. Functors accept functions as parameters and/or return functions as a result. Here it does both: it takes a function that will be used to generate results as needed for new inputs, and returns a function that returns a cached result, first calling the input function to generate the result if needed.
  • The return function uses a closure to maintain its own state. When memo is called it creates two local variables, one to maintain the cache and another for thread safety. The life of these variables is maintained in a context available within the return value, a new function where they are used, but they are inaccessible outside of it. If memo is called again, new instances of these variables are created and maintained in a different context.
  • An option type is used instead of directly using the null type that is native to C#. This concept is called a maybe type in some languages. The cache is checked to see if we have a result for the input parameter. This check returns an option type which is then checked with a match function. If there is a result (the Some match operation) then it is returned. If there is no result (the None match operation) then the input function is called, the result is cached, and then it is returned.

"Life is too short for malloc." - Neal Ford

For a general introduction to functional programming, watch Neal Ford's talk about functional thinking. In this 40 minute introduction he states that "life is too short for malloc." This resonates with me, as someone who worked exclusively in non-managed code for almost 20 years. Low-level languages are certainly necessary but they are not the proper tool for most software development. It was liberating to move from C/C++ to C#, where I could focus on business requirements and let memory management fade to the back of my mind. Likewise moving toward functional rather than imperative programming allows focusing on actions to achieve results -- data transformations -- rather than on lower level steps to modify data. Functional programming provides new ways to think about problems, and this provides immediate benefits to your software development (immutability, testable code, easier concurrency).

Resources I've used for functional programming guidance this week: