# Reduce on recursive function?

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 ?

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)
``````

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

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.

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)

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