Discriminated unions exactly solve this problem (just "inside out" in the same way that Church encodings are algebraic datatypes "inside out"). It's only a matter of whether you have closed or open unions. That then just governs whether you have to nest types or not.

In fact, you can get even more code reuse than with your standard visitor pattern using openly recursive unions.

// This is all pseudo code with open unions to reduce nesting.
// Doable with closed unions, just more cluttered

// Note these are all type aliases, since open unions imply structural types,
// but nonetheless these are truly (open) discriminated unions

// ------ BEGIN : In some external library
type alias Evaluator = PrintEvaluator or ExecutionEvaluator

// Open here is referring to open recursion rather than open unions
// This gives us even more reuse than the standard visitor pattern
type alias ExpressionOpen a = Literal Int or Addition a a

stringEvaluator : ExpressionOpen String -> String
stringEvaluator (Literal n) = intToString n
stringEvaluator (Addition x y) = x ++ " + " ++ y

executionEvaluator : ExpressionOpen Int -> Int
executionEvaluator (Literal n) = n
executionEvaluator (Addition x y) = x + y

evaluate : Evaluator -> Fix ExpressionOpen -> String
// This fold is a generalized version of the usual fold on list, meant to work on fixed point types
evaluate PrintEvaluator expr = fold stringEvaluator expr
evaluate ExecutionEvaluator expr = intToString (fold executionEvaluator expr)

// ------ END : No longer in some external library

// ------ BEGIN : My own code
type alias ComplexEvaluator = HexadecimalEvaluator or Evaluator

hexadecimalEvaluator : ExpressionOpen String -> String
hexadecimalEvaluator (Literal n) = intToHexString n
hexadecimalEvaluator (Addition x y) = x ++ " + " ++ y

type alias ComplexExpressionOpen a = BasicExpressionOpen a or Multiplication a a

extendedEvaluator : ComplexEvaluator -> Fix ExpressionOpen -> String
// This may look like dynamic dispatch but it isn't
// ": Evaluator" expands out to a case match on the union tags of Evaluator
// In both branches of the match we then just call evaluate
extendedEvaluator (evaluator : Evaluator) expr = evaluate evaluator expr
extendedEvaluator HexadecimalEvaluator expr = fold hexadecimalEvaluator expr

stringEvaluatorExtended : ComplexExpressionOpen String -> String
stringEvaluatorExtended (expr : ExpressionOpen String) = stringEvaluator expr
stringEvaluatorExtended (Multiplication x y) = x ++ " * " ++ y

executionEvaluatorExtended : ComplexExpressionOpen Int -> Int
executionEvaluatorExtended (expr : ExpressionOpen Int) = executionEvaluator expr
executionEvaluatorExtended (Multiplication x y) = x * y

hexadecimalEvaluatorExtended : ComplexExpressionOpen String -> String
hexadecimalEvaluatorExtended (expr : ExpressionOpen String) = hexadecimalEvaluator expr
hexadecimalEvaluatorExtended (Multiply x y) = x ++ " * " ++ y

// If you want to extend both evaluator and expression at the same time you need
// to repeat yourself a little
// But you would need to repeat even more with the visitor pattern!
// Namely none of your old evaluators work nor do any of your old expression trees!
evaluateExtendedExpression : ComplexEvaluator -> Fix ComplexExpressionOpen -> String
evaluateExtendedExpression PrintEvaluator expr = fold stringEvaluatorExtended expr
evaluateExtendedExpression ExecutionEvaluator expr = fold executionEvaluatorExtended expr
evaluateExtendedExpression HexadecimalEvaluator expr = fold hexadecimalEvaluatorExtended expr

// ------ END : Finished with my own code