# Reduce on recursive function?

**URL:** <https://discourse.julialang.org/t/reduce-on-recursive-function/24511>\
**Category:** General Usage\
**Created:** [May 23, 2019, 11:17am UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511 "2019-05-23T11:17:07Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [May 23, 2019, 11:17am UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511/1 "2019-05-23T11:17:07Z")

</div>

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

```julia
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 ?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 23, 2019, 11:30am UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511/2 "2019-05-23T11:30:39Z")

</div>

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:

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

```

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [May 23, 2019, 12:11pm UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511/3 "2019-05-23T12:11:19Z")

</div>

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

```julia
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:

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

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 23, 2019, 12:27pm UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511/4 "2019-05-23T12:27:07Z")

</div>

> [@jonathanBieler](#):
>
> 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.

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.

---

<div class="post-metadata">

**Author:** ![yha](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yha/32/3502_2.png) [@yha](https://discourse.julialang.org/u/yha)\
**Post date:** [May 23, 2019, 12:30pm UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511/5 "2019-05-23T12:30:37Z")

</div>

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

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

```

(probably not very efficient, if it matters)

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [May 23, 2019, 12:53pm UTC](https://discourse.julialang.org/t/reduce-on-recursive-function/24511/6 "2019-05-23T12:53:54Z")

</div>

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