Type stable difference of tuples

question

#1

Hello everyone, I am trying to figure out how to take the difference between two tuples of integers in a type-stable way, assuming that, if tuple a has length n, and tuple b has length m, then tuple c = setdiff(a,b) will have length n-m.

With that condition, it seems like it should be possible.


#2

If I’m understanding you correctly…

# Should work, but unfortunately doesn't
overlapping_setdiff{N, M}(a::NTuple{N, Int}, b::NTuple{M, Int})::NTuple{N-M, Int} = 
   tuple(setdiff(a, b)...)

# Type-stable
@generated overlapping_setdiff2{N, M}(a::NTuple{N, Int}, b::NTuple{M, Int}) = 
   :(tuple(setdiff(a, b)...)::NTuple{$(N-M), Int})

overlapping_setdiff2((3,4,5), (4,5))

It’s type-stable but not terribly efficient, since it builds an intermediate array. Is that a problem?


#3

Thanks, I didn’t know about the generated trick! Yeah, I do want it to be efficient. I was also using setdiff, and it is quite slow. I managed to make it faster by using a bitarray, but that still is pretty slow.


#4

Are both your tuples already sorted and have no duplicate elements? If so:

import Base: tail
@inline function sorted_setdiff(t1::Tuple, t2::Tuple)
    if t1[1] == t2[1]
        sorted_setdiff(tail(t1), tail(t2))
    else
        (t1[1], sorted_setdiff(tail(t1), t2)...)
    end
end
@noinline sorted_setdiff(t1::Tuple{}, t2::Tuple) = error("did not find $(t2[1])")
sorted_setdiff(t1::Tuple, ::Tuple{}) = t1
sorted_setdiff(::Tuple{}, ::Tuple{}) = ()

Benchmarks are left to the reader…


#5

Wow that’s really neat! The @code_warntype output of this is pretty crazy but it works perfectly well! Thanks all for your help.


#6

Yeah, don’t call it on large tuples — it creates exponentially large functions. :slight_smile:


Help with type instabilities