以类型安全的方式在集合中存储两种类型的对象

Question

我一直在实现一个增强的Shunting-Yard算法来解析算术表达式.该算法的一个方面是它维护a Queue和a Stack.

在我的实现中,Queue包含Expressions和Operators.在Stack包含Operators和Parenthesis.

Expressions,Parenthesis并且Operators没有任何共同点,保证他们中的任何两个拥有共享接口.

处理办法:

• 我目前的实施包括Expression并Operator实施一个INotParanthesis.Operator并Paranthesis实施一个INotExpression.然后我宣布Queue <INotParanthesis>,和Stack <INotExpression>.

  我不喜欢这种实现 - 这些接口似乎非常适合更清晰的算法代码.我也相信接口应该描述一个对象是什么,而不是它不是什么.

• 另一方面,我也不想使用集合<Object>,因为很难确定这些代码的正确性.

• 唯一一个我想出来的,到目前为止,正在实施我自己NonParanthesisQueue和NonExpressionStack容器.这样做的好处是可以对从这些容器中拉出的对象进行更一致的类型检查 - 而且还有更多代码的缺点.

我的方法有什么合理的替代方案吗？

Answer 1

听起来您真正想要的是 sum 类型。尽管 C# 没有内置这些​​，但您可以使用函数式编程中的一个技巧，称为 Church encoding 来实现这一点。它是完全类型安全的，不涉及强制转换，但是在 C# 中使用它有点奇怪，主要是由于类型推断的限制。

主要技巧是，我们没有使用属性和检查来检索两个备选方案中的一个，而是有一个高阶函数Map，它将两个函数作为参数，并根据存在的备选方案调用适当的一个。以下是您将如何使用它：

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));
}

这是IEither,Left和的实现Right。它们是完全通用的，可以在任何需要求和类型的地方使用。

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);
    }
}

参考：

• 标记联合
• 代数数据类型
• 教堂编码