{{ message }}

Instantly share code, notes, and snippets.

# zenna/cata.jl

Last active Apr 3, 2019
Catamorphism

### jkoppel commented Apr 3, 2019 • edited

 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 commented Apr 3, 2019 • edited

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

### 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 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.