cata2.jl

abstract type Node end

struct Val <: Node
  x::Int
end

cons(::Val, x) = Val(x)
children(val::Val) = ()

struct Add{T1, T2} <: Node
  a::T1
  b::T2
end

cons(::Add, a, b) = Add(a, b)

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

cata_(f, node, children) = f(cons(node, map(x_ -> cata(f, x_), children)...))
cata_(f, node, children::Tuple{}) = f(node)
cata(f, node::T) where T = 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)