How to get extensibility for the Expression Problem using existential types for a heterogeneous list

Question

What I'm trying to do

I'm trying to solve a problem similar to the Expression Problem in haskell.

There are different expressions and different operations for them. Both expressions and operations should be extensible.

My attempt:

Create a type class for expressions and a type class for each operation.

Adding new types of expressions can be done by declaring an instance of the expression type class and also an instance for all supported operation type classes.
Adding a new operation can be done by creating a new type class and declare an instance of it for all expression types that should support that operation.

class Expr a

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

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

Some examples (not that important):

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

Now I need a heterogeneous list of expressions that support all operations. This can be done with an existential type as a wrapper over all these expression types.

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

But now I've lost the extensibility of operations because a new operation would need to be added as a constaint to definition of SomeExpr. In order for SomeExpr to provide all operations, all operations must be given as constraints.

Is there a way to have a heterogeneous list of expressions while still having extensibility of both expression types and operations?
It should also be possible to create the heterogeneous list without knowing the exact types of the expressions at compile time.

Edit: With extensibility I mean defining new types of expressions (like Literal and Add l r), as well as new operations on expressions (like prettyPrint and evaluate) in other modules.