Allow matching with static functions

[iamim]

One issue with .Match is that it allocated objects for case matching functions to capture the closure. C# has a mechanism to prevent this from happening with a static keyword on lambda. However, for it to work the "closure" state has to be threaded manually.

Consider an example of such a match function called .FoldMatch based on your Expression example implemented in the Expression class. Functions StaticEvaluate and EvaluateUniqueVar show how such a utility could be used:

// Adapted from https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/discriminated-unions#using-discriminated-unions-for-tree-data-structures

using System.Collections.Immutable;
using Dunet;
using static Expression;

var environment = new Dictionary<string, int>()
{
    ["a"] = 1,
    ["b"] = 2,
    ["c"] = 3,
};

var expression = new Add(new Variable("a"), new Multiply(new Number(2), new Variable("b")));

// Evaluate a + 2 * b
var result = Evaluate(environment, expression);

Console.WriteLine(result); // 5

static int Evaluate(Dictionary<string, int> env, Expression exp) =>
    exp.Match(
        number => number.Value,
        add => Evaluate(env, add.Left) + Evaluate(env, add.Right),
        multiply => Evaluate(env, multiply.Left) * Evaluate(env, multiply.Right),
        variable => env[variable.Value]
    );

// Allows to evaluate expressions without allocating lambdas
static int StaticEvaluate(Dictionary<string, int> env, Expression exp) =>
    exp.FoldMatch(
        env,
        static (_, number) => number.Value,
        static (e, add) => StaticEvaluate(e, add.Left) + StaticEvaluate(e, add.Right),
        static (e, multiply) => StaticEvaluate(e, multiply.Left) * StaticEvaluate(e, multiply.Right),
        static (e, variable) => e[variable.Value]
    );

// An example of how to thread state through a recursive function
// It simulates a (made up) use case where variables can be used only once
static (IImmutableDictionary<string, int> state, int result) 
    EvaluateUniqueVar(IImmutableDictionary<string, int> env, Expression exp) =>
    exp.FoldMatch(
        env,
        static (e, number) => (e, number.Value),
        static (e, add) =>
        {
            (e, var left) = EvaluateUniqueVar(e, add.Left);
            (e, var right) = EvaluateUniqueVar(e, add.Right);
            
            return (e, left + right);
        },
        static (e, multiply) =>
        {
            (e, var left) = EvaluateUniqueVar(e, multiply.Left);
            (e, var right) = EvaluateUniqueVar(e, multiply.Right);
            
            return (e, left * right);
        },
        static (e, variable) => (e.Remove(variable.Value), e[variable.Value])
    );

[Union]
public partial record Expression
{
    partial record Number(int Value);

    partial record Add(Expression Left, Expression Right);

    partial record Multiply(Expression Left, Expression Right);

    partial record Variable(string Value);
    
    public T FoldMatch<T, TState>(
        TState state,
        Func<TState, Number, T> number,
        Func<TState, Add, T> add,
        Func<TState, Multiply, T> multiply,
        Func<TState, Variable, T> variable
    ) => this switch
    {
        Number x   => number(state, x),
        Add x      => add(state, x),
        Multiply x => multiply(state, x),
        Variable x => variable(state, x),
        _          => throw new InvalidOperationException()
    };
}