treemap is broken?

[Arkoniak]

It looks like treemap is broken or at least maybe documentation example is needed?

using AbstractTrees
import AbstractTrees: children

struct Node
    v::Int
    c::Vector{Node}
end

children(n::Node) = n.c

tree = Node(1,
            [Node(2,
                  [Node(3, []),
                   Node(4, [])]),
             Node(5, [])])

With this setup, I wasn't able to run treemap in any configuration. FIrst of all, it accepts only PostOrderDFS types. Why can't I just pass tree and it internally call PostOrderDFS on it?

Secondly, call like this

treemap(x -> x.v, PostOrderDFS(tree))

return error

ERROR: MethodError: no method matching keys(::PostOrderDFS{Node})
Closest candidates are:
  keys(::Core.SimpleVector) at essentials.jl:605
  keys(::Cmd) at process.jl:639
  keys(::LibGit2.GitTree) at /home/skoffer/.julia/packages/Revise/XFtoQ/src/git.jl:52
  ...
Stacktrace:
 [1] pairs(::PostOrderDFS{Node}) at ./abstractdict.jl:134
 [2] treemap(::var"#19#20", ::PostOrderDFS{Node}) at /home/skoffer/.julia/packages/AbstractTrees/VQ0nX/src/iteration.jl:349

I can pirate it to ( I am completely at loss, what I am doing at this moment, actually)

Base.:pairs(x::PostOrderDFS) = enumerate(x)

This helps to go through this error, but it looks like function require more than one argument, so I change call to

treemap((i, x, c) -> x.v, PostOrderDFS(tree))

And then I get into error

ERROR: MethodError: no method matching copy!(::Array{Int64,1}, ::Int64, ::Array{Union{},1}, ::Int64, ::Int64)
Closest candidates are:
  copy!(::AbstractArray{T,1} where T, ::AbstractArray{T,1} where T) at abstractarray.jl:708
  copy!(::AbstractArray, ::AbstractArray) at abstractarray.jl:711
Stacktrace:
 [1] treemap(::var"#23#24", ::PostOrderDFS{Node}) at /home/skoffer/.julia/packages/AbstractTrees/VQ0nX/src/iteration.jl:369

Help shows that it is true, there is no copy! with 5 arguments in Base.

So, how this function is supposed to be used? Is it working at all?

[pulsipher]

I am running into the same problem, is there a way to properly use this function such that it works?

[jlumpe]

Can either of you tell me what the expected return value of treemap is in this case? I'm a contributor but not the author of this code, and honestly I can't tell what it's supposed to do.

[Arkoniak]

That's a good question. Since from the definition of treemap "maps each node of a tree to obtain a new tree.", it should return new tree, i.e. root node in this case. So, for example, if f is x -> x^2 then this tree

tree = Node(1,
            [Node(2,
                  [Node(3, []),
                   Node(4, [])]),
             Node(5, [])])

should map to

tree2 = Node(1,
             [Node(4,
                   [Node(9, []),
                    Node(16, [])]),
              Node(25, [])])

(and yes, it should return tree2).

It seems though, that treemap is a remnant of old days, when tree structures were defined in the same manner as it is done in lisp, i.e. nested array, so (I maybe made mistakes in brackets, sorry in advance)

tree = [1, [[2, [3, 4]], 5]]

In this case, treemap is just a regular recursive map

treemap(x -> x^2, tree) = [1, [[4, [9, 16]], 25]]

You can see this here: https://github.com/JuliaCollections/AbstractTrees.jl/blob/master/src/iteration.jl#L347

But at the same time, now we do not use this representation for trees, so treemap is just broken. Maybe it should be deprecated? Or completely rewritten. From usage point of view, I think it make sense to define treemap as

treemap(f, tree)

where f should map node to node (where node types are defined by user). For example, square procedure can look like

node -> Node(node.v^2, [])

Then treemap just create all necessary nodes, put them in a proper tree structure and return root node to the user.