Catamorphism

cata.jl

# Simplest Version

abstract type Node end

struct Val <: Node
  x::Int
end

children(val::Val) = ()

struct Add <: Node
  a
  b
end

children(add::Add) = (add.a, add.b)
interpret(val::Val) = val.x
interpret(add::Add) = add.a + add.b

cata_(f, node::T, children) where T = f(T(map(x_ -> cata(f, x_), children)...)) 
cata_(f, node, children::Tuple{}) = f(node)
cata(f, node) = cata_(f, node, children(node))

term = Add(Add(Val(1), Val(2)), Val(3))
cata(interpret, term)


swap(add::Add) = Add(add.b, add.a)
swap(v::Val) = v
cata(swap, term)

julia> abstract type Node end

julia> struct Val <: Node
         x::Int
       end

julia> children(val::Val) = ()
children (generic function with 1 method)

julia> struct Add <: Node
         a
         b
       end

julia> children(add::Add) = (add.a, add.b)
children (generic function with 2 methods)

julia> interpret(val::Val) = val.x
interpret (generic function with 1 method)

julia> interpret(add::Add) = add.a + add.b
interpret (generic function with 2 methods)

julia> cata_(f, node::T, children) where T = f(T(map(x_ -> cata(f, x_), children)...))
cata_ (generic function with 1 method)

julia> cata_(f, node, children::Tuple{}) = f(node)
cata_ (generic function with 2 methods)

julia> cata(f, node) = cata_(f, node, children(node))
cata (generic function with 1 method)

julia> term = Add(Add(Val(1), Val(2)), Val(3))
Add(Add(Val(1), Val(2)), Val(3))

julia> cata(interpret, term)
6

julia> swap(add::Add) = Add(add.b, add.a)
swap (generic function with 1 method)

julia> swap(v::Val) = v
swap (generic function with 2 methods)

julia> cata(swap, term)
Add(Val(3), Add(Val(2), Val(1)))

With the implementation I wrote I don't think it should be Val(v), that would double up the Vals

I misread the code. I deleted that comment before I saw your reply.