# Flattening nested operators in \`Expr\`

**URL:** <https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468>\
**Category:** General Usage\
**Tags:** metaprogramming\
**Created:** [March 22, 2023, 6:16pm UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468 "2023-03-22T18:16:46Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [March 22, 2023, 6:16pm UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/1 "2023-03-22T18:16:46Z")

</div>

I have an `Expr` that comes to me looking like this:

```julia
:((+)((+)(1,2),3))

```

except that my actual `Expr`s have 100s of terms, each of which is a complicated expression (which may involve products with further sums that I don’t want to expand at this level).

Now I actually want to iterate over each term individually and apply some function to each term. Is there an elegant/robust way to do so?

My instinct is to try to turn that expression into a “flattened” version making use of the associativity:

```julia
:((+)(1,2,3))

```

When I do that, I can just iterate over `expr.args[2:end]`. Is this the best approach?

Ideally, I’d like to be able to handle either form without having to worry about it.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [March 22, 2023, 7:48pm UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/2 "2023-03-22T19:48:30Z")

</div>

An expression is basically a tree:

```julia
julia> e = :((+)((+)(1,2),3))
:((1 + 2) + 3)

julia> Meta.dump(e)
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol +
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol +
        2: Int64 1
        3: Int64 2
    3: Int64 3

```

In order to process them, you might want to look at [MacroTools.jl](https://github.com/FluxML/MacroTools.jl) which has some nice tools for walking trees:

```julia
julia> using MacroTools

julia> MacroTools.postwalk(x -> if x isa Number; 2*x else x end, e)
:((2 + 4) + 6)

```

---

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [March 22, 2023, 8:28pm UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/3 "2023-03-22T20:28:43Z")

</div>

Thanks for your reply. I certainly use MacroTools most of the time. The problem is how to _stop it_ from going too far.

I guess my question in your framing would be: How do I stop `postwalk` (or `prewalk`) from going further down a branch in that tree if any of the operations is something other than `(+)`?

So, for example, if my Expr were

```julia
:((+)((+)(1,a*(b+c)),3))

```

how would I ensure that my processing function receives as arguments `1`, `a*(b+c)`, and `3`, but _not_ `(b+c)`, `b`, or `c`?

---

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [March 23, 2023, 3:18am UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/4 "2023-03-23T03:18:36Z")

</div>

Here’s my solution:

```julia
isadd(x) = MacroTools.isexpr(x, :call) && x.args[1] ∈ ((+), :+)

function flatten_add!(expr)
    while any(isadd, expr.args[2:end])
        args = expr.args[2:end]
        i₊ = findfirst(isadd, args)
        args′ = [:+; args[1:i₊-1]; args[i₊].args[2:end]; args[i₊+1:end]]
        expr.args[:] = args′[1:length(expr.args)]
        append!(expr.args, args′[1+length(expr.args):end])
    end
    expr
end

```

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [March 23, 2023, 11:01pm UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/5 "2023-03-23T23:01:26Z")

</div>

This is indeed a bit more involved. You could either use the underlying `walk` function that is used by both `prewalk` and `postwalk` under the hood or insert and strip a marker to prevent `prewalk` from stepping further down in your expression:

```julia
julia> using MacroTools

julia> e = :((+)((+)(1,a*(b+c)),3))
:((1 + a * (b + c)) + 3)

julia> struct StopHere
           stuff
       end

julia> MacroTools.postwalk(x -> if x isa StopHere x.stuff else x end,
                           MacroTools.prewalk(x -> if iscall(x, :+) x else println(x); StopHere(x) end,
                                              e))
+
+
1
a * (b + c)
3
:((1 + a * (b + c)) + 3)

```

---

<div class="post-metadata">

**Author:** ![mongi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mongi/32/43334_2.png) [@mongi](https://discourse.julialang.org/u/mongi)\
**Post date:** [April 15, 2023, 10:22am UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/7 "2023-04-15T10:22:03Z")

</div>

Greetings,  
I understand the solution, but I just want to understand why args[1:i₊-1] 's output is different after the @show in the code. Thanks

```julia
using MacroTools
isadd(x) = MacroTools.isexpr(x, :call) && x.args[1] ∈ ((+), :+)
function flatten_add!(expr)
    while any(isadd, expr.args[2:end])
        args = expr.args[2:end]
        i₊ = findfirst(isadd, args)
        @show args[1:i₊-1] #-------------outputs Any[]
        args′ = [:+; args[1:i₊-1]; args[i₊].args[2:end]; args[i₊+1:end]]
        @show args′[2] #----------- outputs 1
        expr.args[:] = args′[1:length(expr.args)]
        append!(expr.args, args′[1+length(expr.args):end])
    end
    expr
end
flatten_add!(:((+)((+)(1,a*(b+c)),3)))

```

---

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [April 15, 2023, 2:12pm UTC](https://discourse.julialang.org/t/flattening-nested-operators-in-expr/96468/8 "2023-04-15T14:12:22Z")

</div>

First, let’s just review the reason for `args[1:i₊-1]`. It’s to capture any part of the expression _before_ the first “add” _within_ the outer “add”. In your case, the expression is `:((+)((+)(1,a*(b+c)),3))`. The very first thing inside the outer “add” is another “add”, so it makes sense that `args[1:i₊-1]` is empty. If I add an `x` before that first nested “add”, like `:((+)(x,(+)(1,a*(b+c)),3))`, you get a non-empty array there.

Next, step back and remember what a semicolon does inside a vector constructor: [it does vertical concatenation](https://docs.julialang.org/en/v1/manual/arrays/#man-array-concatenation). But concatenating an empty array with other things is (almost) the same as concatenating those other things. Take a simple example:

```julia
julia> [1; []; [2, 3, 4]; 5]
5-element Vector{Any}:
 1
 2
 3
 4
 5

julia> [1; [2, 3, 4]; 5]
5-element Vector{Int64}:
 1
 2
 3
 4
 5

```

The only difference is the eltype of those vectors, but the elements themselves are the same in both cases. (In performance-critical code, of course, we would work harder for type stability, but I’m not worried.)

So, when `args′` is constructed by concatenating that empty vector, it basically just disappears, and `args′[2]` is actually referring to `args[i₊].args[2]`.