CODEWITHSUNDEEP
c#collectionstypesheterogeneous
Vladislav
Vladislav

Reputation: 4966

Type-safe way to store two types of object in a collection

I've been implementing an enhanced Shunting-Yard algorithm for parsing an arithmetic expression. One aspect of the algorithm, is that it maintains a Queue, and a Stack.

In my implementation, the Queue contains Expressions and Operators. The Stack contains Operators and Parenthesis.

Expressions, Parenthesis, and Operators have nothing in common that warrants any two of them having a shared interface.

Approaches:

Are there any reasonable alternatives to my approaches?

Upvotes: 5

Views: 978

Answers (2)

hammar
hammar

Reputation: 139830

It sounds like what you really want is a sum type. Although C# does not have these built in, there's a trick from functional programming that you can use called Church encoding to achieve this. It's completely type safe with no casts involved, however it's a bit weird to use in C# mostly due to the limitations of the type inference.

The main trick is that instead of using properties and checks to retrieve one of the two alternatives, we have a higher order function Map that takes two functions as arguments and calls the appropriate one depending on which alternative was present. Here's how you would use it:

var stack = new Stack<IEither<Operator, Parenthesis>>();

stack.Push(new Left<Operator, Parenthesis>(new Operator()));
stack.Push(new Right<Operator, Parenthesis>(new Parenthesis()));

while (stack.Count > 0)
{
    stack.Pop().Map(op  => Console.WriteLine("Found an operator: " + op),
                    par => Console.WriteLine("Found a parenthesis: " + par));
}

Here's the implementation of IEither, Left and Right. They are fully generic and could be used anywhere you want a sum type.

public interface IEither<TLeft, TRight>
{
    TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight);
    void Map(Action<TLeft> onLeft, Action<TRight> onRight);
}

public sealed class Left<TLeft, TRight> : IEither<TLeft, TRight>
{
    private readonly TLeft value;

    public Left(TLeft value)
    {
        this.value = value;
    }

    public TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight)
    {
        return onLeft(value);
    }

    public void Map(Action<TLeft> onLeft, Action<TRight> onRight)
    {
        onLeft(value);
    }
}

public sealed class Right<TLeft, TRight> : IEither<TLeft, TRight>
{
    private readonly TRight value;

    public Right(TRight value)
    {
        this.value = value;
    }

    public TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight)
    {
        return onRight(value);
    }

    public void Map(Action<TLeft> onLeft, Action<TRight> onRight)
    {
        onRight(value);
    }
}

References:

Upvotes: 4

rationull
rationull

Reputation: 475

Maybe you could define a small holder type for each, one with an Expression property and an Operator property and the other with an Operator property and a Parenthesis property. Accessors and constructors could assert or otherwise ensure that only one is populated. The queue and the stack would each contain the appropriate holder type.

A little awkward but typesafe and workable.

Hopefully someone will have a more clever idea.

Upvotes: 1

Related Questions