Haskell存在类型实现异构列表时如何保障表达式问题双向可扩展性

实现目标 #

我尝试在Haskell中解决与表达式问题（Expression Problem）类似的问题：系统存在多种表达式类型，以及作用于表达式的多种操作，要求表达式类型与操作二者均具备可扩展性。

现有尝试方案 #

我为表达式定义了独立的类型类，同时为每一类操作单独定义对应的类型类：

• 新增表达式类型时，仅需为该类型声明Expr类型类实例，同时为所有需要支持的操作类型类声明对应实例即可；
• 新增操作时，仅需定义新的操作类型类，同时为所有需要支持该操作的表达式类型声明对应实例即可。

基础类型类定义如下：

class Expr a

class (Expr a) => PrettyPrint a where
    prettyPrint :: a -> String

class (Expr a) => Evaluate a where
    evaluate :: a -> Int

非核心逻辑的简单实现示例：

newtype Literal = Literal Int
instance Expr Literal

data Add l r = Add l r
instance (Expr l, Expr r) => Expr (Add l r)

instance PrettyPrint Literal where
    prettyPrint (Literal x) = show x

instance Evaluate Literal where
    evaluate (Literal x) = x

instance (PrettyPrint l, PrettyPrint r) => PrettyPrint (Add l r) where
    prettyPrint (Add left right) = "(" ++ prettyPrint left ++ " + " ++ prettyPrint right ++ ")"

instance (Evaluate l, Evaluate r) => Evaluate (Add l r) where
    evaluate (Add left right) = evaluate left + evaluate right

当前需求是构造一个支持所有操作的表达式异构列表（heterogeneous list），最初采用存在类型（existential type）作为所有表达式类型的包装器实现该需求，代码如下：

data SomeExpr = forall a. (Expr a, PrettyPrint a, Evaluate a) => SomeExpr a

instance Expr SomeExpr

instance PrettyPrint SomeExpr where
    prettyPrint (SomeExpr x) = prettyPrint x
    
instance Evaluate SomeExpr where
    evaluate (SomeExpr x) = evaluate x

但该实现丢失了操作维度的可扩展性：新增操作时必须将该操作对应的约束添加到SomeExpr的定义中，只有将所有操作都写入约束列表，SomeExpr才能对外提供全部操作能力。

核心疑问：是否存在一种实现方式，既能构造表达式的异构列表，又能同时保留表达式类型、操作两个维度的可扩展性？
额外要求：构造异构列表时无需在编译期确定列表内表达式的具体类型。

补充说明：此处提到的可扩展性，指支持在其他模块中定义新的表达式类型（如Literal、Add l r），以及新的表达式操作（如prettyPrint、evaluate）。

内容的提问来源于stack exchange，提问作者IzzDarki