PatternMatchingCollections

Pattern Matching

Succinc<T> pattern matching guide: Collections

Introduction

This pattern matching guide is split into the following sections:

Pattern matching on collections - Covered here.
Pattern matching on discriminated unions.
Pattern matching on Either<TLeft, TRight>.
Pattern matching on options
Pattern matching on Success<T>
Pattern matching on tuples
Pattern matching on ValueOrError
Type-based pattern matching for all other types
Value-based pattern matching on all other types

WARNING This document is still work in progress. Having added "cons pattern matching" support for collections, I'm now having major doubts as to its usefulness. So I've left completing this page to a later date. If you come across this and have a real use-case for cons pattern matching that isn't already handled by linq, then raise an issue please so we can discuss it.

Due to the way C# resolves extension methods, this feature is currently limited to collections referenced via one of the following data types:

IEnumerable<T>
IList<T>
List<T>

Not that whilst eg an array implements IEnumerable<T>, it isn't accessible to an array directly. It needs casting to IEnumerable<T> to access it. If this is a problem for you, please raise an issue and it'll be considered for a future release.

Succinc<T> supports two types of pattern matching on collections: "cons matching" and "match mapping". These are explained separately, below.

"Cons matching" Syntax

The generalised syntax for "cons matching" collection patterns can be expressed using BNF-like syntax. Unlike with all Succinc<T> pattern matching cases, only matching and returning a value is supported for cons matching. Statement-based matching isn't supported:

result = {collection}.Match().To<{result type}>()
    [EmptyExpression|SingleExpression|ConsExpression]...
    .Result();

EmptyExpression ==>
    .Empty().Do({result type expression})

SingleExpression ==>
    .Single()[SingleWhereExpression].Do({value} => {result type expression}) |
    .Single()[SingleWhereExpression].Do({result type expression})

ConsExpression ==>
    .Cons()[ConsWhereExpression].Do(({head},{tail}) => {result type expression}) |
    .Cons()[ConsWhereExpression].Do({result type expression})

SingleWhereExpression ==>
    .Where({item} => {boolean expression}) |
    .Where({item} => {boolean expression})

ConsWhereExpression ==>
    .Where(({head},{tail}) => {boolean expression}) |
    .Where(({head},{tail}) => {boolean expression})

To explain the above syntax:

{} denotes a non-literal, eg {void expression} could be the empty expression, {}, or something like Console.WriteLine("hello").
Items in [] are optional.
| is or, ie [x|y] reads as "an optional x or y".
... after [x] means 0 or more occurrences of x.
==> is a sub-rule, which defines the expression on the left of this symbol.

Basic Usage

The most basic form is matching on which type a union contains:

var list = new [] {1, 2, 3, 4, 5};

int SumListContents(IEnumerable<int> collection) 
    => collection.Match().To<int>()
                 .Single().Do(x => x)
                 .Cons().Do((head, tail) => head + SumListContents(tail))
                 .Result();

var result = SumListContents(list);

In ContainsRectangle, we test against Case1() (rectangle) and Case2() (circle) to return true/false accordingly. In PrintShape, we test against Case1() and Case2() once more, and invoke an action to print the shape type that corresponds to the union's state.

In both cases, we have used both Case1() and Case2(), but we could optionally use Else():

public static bool ContainsRectangle(Union<Rectangle, Circle> shape) =>
    shape.Match<bool>()
         .Case1().Do(x => true)
         .Else(x => false)
         .Result();

public static void PrintShape(Union<Rectangle, Circle> shape) =>
    shape.Match()
         .Case2().Do(Console.WriteLine("Circle"))
         .Else(Console.WriteLine("Rectangle"))
         .Exec();

Else() or IgnoreElse() is invoked if there is no match from any specified Case1() or Case2() expressions respectively.

One further change can be made to the functional example. We are supplying a parameter, x, which isn't then used. In this case, we can dispense with the lambda and just specify the return value:

public static bool ContainsRectangle(Union<Rectangle, Circle> shape) =>
    shape.Match<bool>()
         .Case1().Do(true)
         .Else(false)
         .Result();

Matching Individual Values

The previous examples just matched each case of the union with any value. We might want to match specific values though. We can use this feature as part of a simple calculator:

public static ExpressionNode CreateExpressionNode(Union<string, float> token) =>
    token.Match<ExpressionNode>()
         .Case1().Of("+").Do(new ExpressionNode(x, y => x + y))
         .Case1().Of("-").Do(new ExpressionNode(x, y => x - y))
         .Case1().Of("/").Do(new ExpressionNode(x, y => x / y))
         .Case1().Of("*").Do(new ExpressionNode(x, y => x * y))
         .Else(x => new ExpressionNode(x))
         .Result();

CreateExpressionNode will create an instance of some type, ExpressionNode, that takes either a Func<float, float, float> or float parameter. For the former, it constructs a lambda function to perform the appropriate calculation. For the latter, it just stores the number supplied.

It's often the case that more than one value needs to match a particular pattern. We have two choices here: we can use Or() or Where().

Firstly, using Or we could write a more advanced CreateExpressionNode method:

public static ExpressionNode CreateExpressionNode(Union<string, float> token) =>
    token.Match<ExpressionNode>()
         .Case1().Of("+").Or("-".Or("*").Or("/").Do(ArithmaticExpression)
         .Case1().Of("(").Do(new ExpressionNode(SpecialAction.StartGroup))
         .Case1().Of(")").Do(new ExpressionNode(SpecialAction.EndGroup))
         .Else(x => new ExpressionNode(x))
         .Result();
}

Here we now match +, -, / and * together and invoke a method ArithmaticExpression that returns one of the four previously described lambdas. ExpressionNode now accepts an enum SpecialAction too, which is used to denote the start and end of a grouping (via ()).

If we want to check a range of values, we can use Where:

public static void PositiveOrNegative(Union<string, int> token) =>
    data.Match()
        .Case2().Where(i => i < 0).Do(_ => Console.WriteLine("Negative"))
        .Case2().Where(i => i > 0).Do(_ => Console.WriteLine("Positive"))
        .Case2().Do(_ => Console.WriteLine("Zero"))
        .Else("Not a number")
        .Exec();

Match Order

So far, we have only considered distinct match patterns, ie where there is no overlap. In many cases, more than one Case1() or Case2() pattern will be required and the match patterns may overlap. The following function highlights this:

public static string OddOrNegative(Union<string, int> token) =>
    data.Match<string>()
        .Case2().Where(i => i % 2 == 1).Do(_ => Console.WriteLine("Odd"))
        .Case2().Where(i => i < 0).Do(_ => Console.WriteLine("Negative"))
        .Else("Neither")
        .Result();

Clearly in this situation, all negative odd integers will match both Where clauses. The matching mechanism tries each match in the order specified and stops on the first match. So OddOrPositive(new Union<string, int>(-1)) will return Odd, rather than Negative.

CaseOf<type> Usage

The following sections detail the basic usage, matching individual values, match order and handling invalid types for CaseOf<type>. CaseN usage can be found here.

Basic Usage

The most basic form is matching on which type a union contains:

public static bool ContainsRectangle(Union<Rectangle, Circle> shape) =>
    shape.Match<bool>()
         .CaseOf<Rectange>().Do(x => true)
         .CaseOf<Circle>().Do(x => false)
         .Result();

public static void PrintShape(Union<Rectangle, Circle> shape) =>
    shape.Match()
         .CaseOf<Rectangle>().Do(Console.WriteLine("Rectangle"))
         .CaseOf<Circle>().Do(Console.WriteLine("Circle"))
         .Exec();

In ContainsRectangle, we test against CaseOf<Rectangle>() and CaseOf<Circle>() to return true/false accordingly. In PrintShape, we test against CaseOf<Rectangle>() and CaseOf<Circle>() once more, and invoke an action to print the shape type that corresponds to the union's state.

In both cases, we have used both CaseOf<Rectangle>() and CaseOf<Circle>(), but we could optionally use Else():

public static bool ContainsRectangle(Union<Rectangle, Circle> shape) =>
    shape.Match<bool>()
         .CaseOf<Rectangle>().Do(x => true)
         .Else(x => false)
         .Result();

public static void PrintShape(Union<Rectangle, Circle> shape) =>
    shape.Match()
         .CaseOf<Circle>().Do(Console.WriteLine("Circle"))
         .Else(Console.WriteLine("Rectangle"))
         .Exec();

Else() or IgnoreElse() is invoked if there is no match from any specified CaseOf<type>() expressions.

One further change can be made to the functional example. We are supplying a parameter, x, which isn't then used. In this case, we can dispense with the lambda and just specify the return value:

public static bool ContainsRectangle(Union<Rectangle, Circle> shape) =>
    shape.Match<bool>()
         .CaseOf<Rectangle>().Do(true)
         .Else(false)
         .Result();

Matching Individual Values

The previous examples just matched each case of the union with any value. We might want to match specific values though. We can use this feature as part of a simple calculator:

public static ExpressionNode CreateExpressionNode(Union<string, float> token) =>
    token.Match<ExpressionNode>()
         .CaseOf<string>().Of("+").Do(new ExpressionNode(x, y => x + y))
         .CaseOf<string>().Of("-").Do(new ExpressionNode(x, y => x - y))
         .CaseOf<string>().Of("/").Do(new ExpressionNode(x, y => x / y))
         .CaseOf<string>().Of("*").Do(new ExpressionNode(x, y => x * y))
         .Else(x => new ExpressionNode(x))
         .Result();

CreateExpressionNode will create an instance of some type, ExpressionNode, that takes either a Func<float, float, float> or float parameter. For the former, it constructs a lambda function to perform the appropriate calculation. For the latter, it just stores the number supplied.

It's often the case that more than one value needs to match a particular pattern. We have two choices here: we can use Or() or Where().

Firstly, using Or we could write a more advanced CreateExpressionNode method:

public static ExpressionNode CreateExpressionNode(Union<string, float> token) =>
    token.Match<ExpressionNode>()
         .CaseOf<string>().Of("+").Or("-".Or("*").Or("/").Do(ArithmaticExpression)
         .CaseOf<string>().Of("(").Do(new ExpressionNode(SpecialAction.StartGroup))
         .CaseOf<string>().Of(")").Do(new ExpressionNode(SpecialAction.EndGroup))
         .Else(x => new ExpressionNode(x))
         .Result();

Here we now match +, -, / and * together and invoke a method ArithmaticExpression that returns one of the four previously described lambdas. ExpressionNode now accepts an enum SpecialAction too, which is used to denote the start and end of a grouping (via ()).

If we want to check a range of values, we can use Where:

public static void PositiveOrNegative(Union<string, int> token) =>
    data.Match()
        .CaseOf<int>().Where(i => i < 0).Do(_ => Console.WriteLine("Negative"))
        .CaseOf<int>().Where(i => i > 0).Do(_ => Console.WriteLine("Positive"))
        .CaseOf<int>().Do(_ => Console.WriteLine("Zero"))
        .Else("Not a number")
        .Exec();

Match Order

So far, we have only considered distinct match patterns, ie where there is no overlap. In many cases, more than one CaseOf<SomeType>() pattern will be required and the match patterns may overlap. The following function highlights this:

public static string OddOrNegative(Union<string, int> token) => 
    data.Match<string>()
        .CaseOf<int>().Where(i => i % 2 == 1).Do(_ => Console.WriteLine("Odd"))
        .CaseOf<int>().Where(i => i < 0).Do(_ => Console.WriteLine("Negative"))
        .Else("Neither")
        .Result();

Clearly in this situation, all negative odd integers will match both Where clauses. The matching mechanism tries each match in the order specified and stops on the first match. So OddOrPositive(new Union<string, int>(-1)) will return Odd, rather than Negative.

Handling unsupported types

CaseOf<type>() patterns can only be tested for type validity at runtime. This means the following code will compile, but will throw an InvalidCaseOfTypeException at runtime, when trying to handle CaseOf<DateTime>():

public static string OddOrNegative(Union<string, int> token) => 
    data.Match<string>()
        .CaseOf<int>().Where(i => i % 2 == 1).Do(_ => Console.WriteLine("Odd"))
        .CaseOf<DateTime>().Do("Will produce an exception here")
        .Else("Neither")
        .Result();

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

PatternMatchingCollections