Reduce on recursive function?

General Usage
1

Sometimes I want to recursively traverse a structure and collect elements along the way, an example is this function that collects all the concret subtypes of a type T:

function allsubtypes(T::Type)
    isconcretetype(T) && return [T]
    out = Type[]
    map(K->allsubtypes(K,out), subtypes(T))
    out
end

allsubtypes(T,out) = isconcretetype(T) ? push!(out,T) : map(K->allsubtypes(K,out), subtypes(T))

As you can see the two methods are very similar, the only difference is that the first one initialize the output. This looks like something that could dealt with with reduce or something similar, but I haven’t manage to find a solution. Is there a nicer pattern to do this ?

2

While this pattern can be done in a more compact way, it is fine as is. Perhaps I would use a Set, unless interested in duplicates:

function allsubtypes!(out, T)
    if isconcretetype(T)
        push!(out, T)
    else
        for S in subtypes(T)
            allsubtypes!(out, S)
        end
    end
    out
end

allsubtypes(T) = allsubtypes!(Set{Type}(), T)
3

That works too yes, I was thinking more along the lines of:

allsubtypes(T) = isconcretetype(T) ? T : (allsubtypes(K) for K in subtypes(T))
recursive_reduce(vcat, allsubtypes(Integer))

Basically these methods always boils down to 1. Initializing the ouput 2. running your logic and 3. returning the ouput. Ideally one would be able to define 2. only and have a higher order function does the rest.

Actually this almost does it:

allsubtypes(T) = isconcretetype(T) ? (T,) : (allsubtypes(K) for K in subtypes(T))

julia> collect(Iterators.flatten(allsubtypes(Integer)))
12-element Array{Any,1}:
 Bool
 (BigInt,)
 (Int128,)
 (Int16,)
 (Int32,)
 (Int64,)
 (Int8,)
 (UInt128,)
 (UInt16,)
 (UInt32,)
 (UInt64,)
 (UInt8,)
1 Like
4

Possibly, but as you have shown, just implementing this is not that complicated anyway. I don’t see a pressing need for recursive_reduce, especially as the “running your logic” part is the only complex part (you generate the tree and accumulate parts of it at the same time), and that would need to be written anyway.

5

Your definition is a bit inconsistent because you include T itself only when it’s concrete.
This should work:

allsubtypes(T) = (s = subtypes(T); union(s, (allsubtypes(K) for K in s)...))

(probably not very efficient, if it matters)

6

Right, in that case I wanted only the concret subtypes, so that’s why I this way.