Skip to content

Instantly share code, notes, and snippets.

@zenna

zenna/cata.jl

Last active Apr 3, 2019
Embed
What would you like to do?
Catamorphism
# 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)
@jkoppel

This comment has been minimized.

Copy link

@jkoppel jkoppel commented Apr 3, 2019

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.

@zenna

This comment has been minimized.

Copy link
Owner Author

@zenna zenna commented Apr 3, 2019

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

@zenna

This comment has been minimized.

Copy link
Owner Author

@zenna zenna commented Apr 3, 2019

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)))
@jkoppel

This comment has been minimized.

Copy link

@jkoppel jkoppel commented Apr 3, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment