@nloops, but for n-1 indices

I’m writing a function where I want to use Base.Cartesian.@nloops to collect possible combinations of inputs, but the object I am creating has one index with a fixed value. Here is a function that does something similar to what I’m after:

using Base.Cartesian: @nloops, @ntuple
function looptest(i)
    @nloops 3 d _ -> (true, false) begin
        println(@ntuple 3 k -> k == i ? 2 : d_k ? 0 : 1)
    end
end

The function creates a 3-element tuple, but one of the three elements has a fixed value that does not vary through the loops. The output looks like this:

julia> looptest(2)
(0, 2, 0)
(1, 2, 0)
(0, 2, 0)
(1, 2, 0)
(0, 2, 1)
(1, 2, 1)
(0, 2, 1)
(1, 2, 1)

I would like to end up with something that does not duplicate each tuple:

julia> looptest(2)
(0, 2, 0)
(1, 2, 0)
(0, 2, 1)
(1, 2, 1)

I’ve hit a wall in trying to work out how to do this using the tools in Base.Cartesian. I thought initially I could reduce the number of loops by 1:

function looptest(i)
    @nloops 2 d _ -> (true, false) begin
        println(@ntuple 3 k -> k == i ? 2 : d_k ? 0 : 1)
    end
end

But then d_3 is not defined. If I could somehow interpolate the fixed index i, a condition would ensure each tuple is only created once. The desired interpolation would be something like this:

function looptest(i)
    @nloops 3 d _ -> (true, false) begin
        if d_$i
            println(@ntuple 3 k -> k == i ? 2 : d_k ? 0 : 1)
        end
    end
end

But this throws ERROR: LoadError: syntax: "$" expression outside quote around .... I’ve searched around for a bit and can’t figure out how to get an interpolation like this to work.

Is there some way I can combine @nloops and @ntuple to get the desired result? Or is there an alternative approach that would work better? Any direction would be much appreciated!


Background: I’m writing a function to compute the vertices of a KDTree from NearestNeighbors.jl. I’ve written a function using the above approach that works for a given HyperRectangle, but I want to extend it to compute only the new vertices created by child nodes. The fixed index is the KDNode.split_dim.

Without using @nloops, this solution does what you want, but in a type-unstable way. I don’t know how to make @nloops/@ntuple worth the way you’d like, or whether it’s even possible.

function looptest2(n, i)
    firstparts = Iterators.product(fill(0:1, i-1)...)
    endparts = Iterators.product(fill(0:1, n-i)...)
    [(f..., 2, e...) for f in firstparts for e in endparts]
end


julia> looptest2(3, 2)
4-element Vector{Tuple{Int64, Int64, Int64}}:
 (0, 2, 0)
 (0, 2, 1)
 (1, 2, 0)
 (1, 2, 1)
tuple.([0,1],[2],[0;;;1])[:]

You want to control the range for that index to be a fixed value, so do it via a check in the rangeexpr of @nloops:

julia> function looptest(i)
           @nloops 3 d j -> j == i ? 2 : (true, false) begin
               println(@ntuple 3 k -> d_k == 2 ? 2 : (d_k ? 0 : 1))
           end
       end
looptest (generic function with 1 method)

julia> looptest(2)
(0, 2, 0)
(1, 2, 0)
(0, 2, 1)
(1, 2, 1)

There’s a bit of redundancy with the check again in @ntuple, which can be removed by doing it this way instead:

    @nloops 3 d j -> j == i ? 2 : (false, true) begin
               println(@ntuple 3 k -> Int(d_k))
     end

but I’ve kept it explicit in the previous version intentionally. You might be able to remove the redundancy (if you want to for the sake of elegance - it’s just a tiny compile-time check anyway) in your actual code depending on what your actual range is.

1 Like

FWIW, the following one-liner function seems to output the same results for the example provided:

looptest(i) = collect(Iterators.product(Tuple(circshift([2, 0:1, 0:1], i-1))...))[:]
Results
julia> looptest(1)
4-element Vector{Tuple{Int64, Int64, Int64}}:
 (2, 0, 0)
 (2, 1, 0)
 (2, 0, 1)
 (2, 1, 1)

julia> looptest(2)
4-element Vector{Tuple{Int64, Int64, Int64}}:
 (0, 2, 0)
 (1, 2, 0)
 (0, 2, 1)
 (1, 2, 1)

julia> looptest(3)
4-element Vector{Tuple{Int64, Int64, Int64}}:
 (0, 0, 2)
 (1, 0, 2)
 (0, 1, 2)
 (1, 1, 2)
1 Like

Much better than my version! With a few modifications it can even be made type stable

looptest(i) = vec(collect(Iterators.ProductIterator(NTuple{3, typeof(2:2)}(circshift([2:2, 0:1, 0:1], i-1)))))
Code warntype
Variables
  #self#::Core.Const(looptest_raf2)
  i::Int64

Body::Vector{Tuple{Int64, Int64, Int64}}
1 ─ %1  = Base.Iterators.ProductIterator::Core.Const(Base.Iterators.ProductIterator)
│   %2  = (2:2)::Core.Const(2:2)
│   %3  = Main.typeof(%2)::Core.Const(UnitRange{Int64})
│   %4  = Core.apply_type(Main.NTuple, 3, %3)::Core.Const(Tuple{UnitRange{Int64}, UnitRange{Int64}, UnitRange{Int64}})
│   %5  = (2:2)::Core.Const(2:2)
│   %6  = (0:1)::Core.Const(0:1)
│   %7  = (0:1)::Core.Const(0:1)
│   %8  = Base.vect(%5, %6, %7)::Vector{UnitRange{Int64}}
│   %9  = (i - 1)::Int64
│   %10 = Main.circshift(%8, %9)::Vector{UnitRange{Int64}}
│   %11 = (%4)(%10)::Tuple{UnitRange{Int64}, UnitRange{Int64}, UnitRange{Int64}}
│   %12 = (%1)(%11)::Base.Iterators.ProductIterator{Tuple{UnitRange{Int64}, UnitRange{Int64}, UnitRange{Int64}}}
│   %13 = Main.collect(%12)::Array{Tuple{Int64, Int64, Int64}, 3}
│   %14 = Main.vec(%13)::Vector{Tuple{Int64, Int64, Int64}}
└──       return %14

Edit: a different (arguably simpler) modification that makes it stable:

function tuple_circshift(t, k)
    for i in 1:k
        t = (last(t), t[1:end-1]...)
    end
    t
end

looptest(i) = vec(collect(Iterators.ProductIterator(tuple_circshift((2:2, 0:1, 0:1), i-1))))

It’s much faster this way as well!

1 Like

What about:

julia> function looptest(i)
           ranges = ntuple(j -> j == i ? (2:2) : (0:1), 3)
           for el in Iterators.product(ranges...)
               println(el)
           end
       end
looptest (generic function with 1 method)

julia> looptest(2)
(0, 2, 0)
(1, 2, 0)
(0, 2, 1)
(1, 2, 1)

This is non-allocating as an iterator:

julia> function looptest2(i)
           ranges = ntuple(j -> j == i ? (2:2) : (0:1), 3)
           s = 0
           for el in Iterators.product(ranges...)
              s += sum(el)
           end
           s
       end
looptest2 (generic function with 1 method)

julia> @btime looptest2(3)
  3.949 ns (0 allocations: 0 bytes)
12