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)

Took me a while to figure out why you had the case on line 21.

It's because the children function drops the integer contained within a Val node. In general, other nodes may have mixture of subnodes and concrete values; only the subnodes should be recursed on.

You'll need to use fmap instead of children. fmap works like this:

fmap(add::Add, f) = Add(f(add.a), f(add.b))
fmap(val::Val, f) = val # Alternatively, Val(val.x)

Then you write cata like this:

cata(f, node) = f(fmap(node, x_ -> cata(f, x_)))

And that is a correct implementation of catamorphisms/generalized folds in Julia.

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

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.