Are there idioms in Julia for fast Algebraic Data Types (ADT)?

General Usage
15

Update: I found a way to encode closed recursive ADTs in Julia and benchmarked this solution against a naive solution. Unfortunately, it performs worse (4.7μs vs 3.3μs for the naive solution), probably due to having to do more allocations.

If anyone finds a better way, please tell me!

Naive solution

abstract type Expression end

struct Const <: Expression
    value :: Int
end

struct Var <: Expression
    varname ::String
end

struct Add <: Expression
    lhs :: Expression
    rhs :: Expression
end

evaluate(e::Const, env) = e.value
evaluate(e::Var, env) = env[e.varname]
evaluate(e::Add, env) = evaluate(e.lhs, env) + evaluate(e.rhs, env)

function sum_of_ints(n)
    if n == 1
        return Const(1)
    else
        return Add(Const(n), sum_of_ints(n - 1))
    end
end

using BenchmarkTools
@btime evaluate(sum_of_ints(100), Dict{String, Int}())

3.228 μs (202 allocations: 5.23 KiB)

Solution that encodes recursive closed ADTs

struct Const
    value :: Int
end

struct Var
    varname ::String
end

struct Add{E}
    lhs :: E
    rhs :: E
end

struct Expression
    ctor :: Union{Const, Var, Add{Expression}}
end

mkConst(value) = Expression(Const(value))
mkAdd(lhs, rhs) = Expression(Add{Expression}(lhs, rhs))
mkVar(var) = Expression(Var(var))

evaluate(e::Expression, env) = evaluate(e.ctor, env)
evaluate(e::Const, env) = e.value
evaluate(e::Var, env) = env[e.varname]
evaluate(e::Add, env) = evaluate(e.lhs, env) + evaluate(e.rhs, env)

function sum_of_ints(n)
    if n == 1
        return mkConst(1)
    else
        return mkAdd(mkConst(n), sum_of_ints(n - 1))
    end
end

using BenchmarkTools
@btime evaluate(sum_of_ints(100), Dict{String, Int}())

4.681 μs (396 allocations: 8.25 KiB)