# Type intersection with `NTuple{len,Any}`

Problem: say I have a type `T` such that `T <: Tuple`, and `len`, a nonnegative `Int` value. I want the intersection of `T` and `NTuple{len,Any}`.

Is it possible to solve the above correctly and exactly? I have three candidate solutions, but I don’t know if either of them is correct (or exact). I’m fine with an answer that would depend on the current state of the Julia master branch, because this question regards a potential PR to Julia.

One approach, giving rise to `tuple_intersect_1` and `tuple_intersect_2` below, is to simply call `typeintersect`. Even though `typeintersect` is not exact in general, maybe it is for this specific problem?

The other approach, giving rise to `tuple_intersect_3` below, is to subtract (using `Base.typesplit`) all the unwanted tuple lengths. I’m not sure if this is correct for all possible types `T`.

The three candidate solutions:

``````struct NegativeLength <: Exception end

function ntuple_intersect_1(::Type{T}, ::Val{len}) where {T, len}
signbit(len::Int) && throw(NegativeLength())
S = NTuple{len,Any}
typeintersect(S, T)::Type{<:S}::Type{<:T}::Type{<:Tuple}
end

function ntuple_intersect_2(::Type{T}, ::Val{len}) where {T, len}
signbit(len::Int) && throw(NegativeLength())
S = NTuple{len,Any}
typeintersect(T, S)::Type{<:S}::Type{<:T}::Type{<:Tuple}
end

function ntuple_intersect_3(::Type{T}, ::Val{len}) where {T, len}
signbit(len::Int) && throw(NegativeLength())
Union{}
end

"""
typesplit(A::Type, B::Type)

Like `Base.typesplit`.
"""
function typesplit end

typesplit( ::Type{A}, ::Type{B}) where {B, A<:B} = Union{}
typesplit(a::Type,    ::Type) = a

function typesplit(a::Union,  b::Type)
l = typesplit(a.a, b)::Type{<:a}
r = typesplit(a.b, b)::Type{<:a}
Union{l, r}::Type{<:a}
end

"""
ntuple_any(v::Val)

Like `ntuple(Returns(Any), v)`.
"""
function ntuple_any end

ntuple_any(::Val{0}) = ()
function ntuple_any(::Val{n}) where {n}
(n::Int ≤ 0) && error("unexpected")
m = n - 1
t = ntuple_any(Val(m))::NTuple{m,DataType}
(Any, t...)::NTuple{n,DataType}
end

"""
tuple_va_type_length_or_more(::Val)

Creates a `Vararg` `<:Tuple` type of specified minimal length.
"""
tuple_va_type_length_or_more(::V) where {V<:Val} = Tuple{ntuple_any(V())..., Vararg}

recursive_typesplit(::Type{T}, ::Val{0}) where {T<:Tuple} = T
function recursive_typesplit(::Type{T}, ::Val{len}) where {T<:Tuple, len}
n = len - 1
S = NTuple{n, Any}
TT = Type{<:T}
TTup = Type{<:Tuple}
R = typesplit(T, S)::TT::TTup
recursive_typesplit(R, Val(n))::TT::TTup
end

function ntuple_intersect_3(::Type{T}, ::Val{len}) where {T<:Tuple, len}
signbit(len::Int) && throw(NegativeLength())
TT = Type{<:T}
TTup = Type{<:Tuple}
More = tuple_va_type_length_or_more(Val(len + 1))::TTup
A = typesplit(T, More)::TT::TTup
recursive_typesplit(A, Val(len))::TT::TTup
end
``````

Test suite (all tests pass, for all three candidates):

``````using Test

field_types(::Type{T}, ::V) where {T, V<:Val} = ntuple((i -> fieldtype(T, i)), V())
ftypes(f::F, ::Type{T}, v::V) where {F, T, V<:Val} = field_types(f(T, v), v)

@testset "ntuple_intersect" begin
T = Union{
Tuple{}, Tuple{Int64}, Tuple{Float64}, Tuple{UInt8,String}, Tuple{Bool,Bool,Bool,Bool},
Tuple{Vararg{Int8}}, Tuple{Int16,Vararg{Int16}}, (Tuple{X,X,Vararg{X}} where {X<:Int32}),
}
funcs = (ntuple_intersect_1, ntuple_intersect_2, ntuple_intersect_3)
@testset "f: \$f" for f ∈ funcs
@testset "non-`Tuple` type" begin
@testset "NT: \$NT" for NT ∈ (Union{}, Int32, Union{Int8,Int32})
@test f(NT, Val(0)) == f(NT, Val(1)) == f(NT, Val(2)) == Union{}
end
end

@testset "`Tuple` type" begin
@test ftypes(f, T, Val(0)) === ()
@test ftypes(f, T, Val(1)) == (Union{Int64, Float64, Int8, Int16},)
@test ftypes(f, T, Val(2)) == (
Union{UInt8,Int8,Int16,Int32}, Union{String,Int8,Int16,Int32},
)
@test ftypes(f, T, Val(3)) ==
let U = Union{Int8,Int16,Int32}
(U, U, U)
end
@test ftypes(f, T, Val(4)) ==
let U = Union{Bool,Int8,Int16,Int32}
(U, U, U, U)
end
end
end
end;
``````

One possibility in particular that’s a bit worrying is `UnionAll` appearing somewhere in `T`. Could that make some of the candidates misbehave?

EDIT: the first two candidates deal with `Vararg` differently than the third candidate: the third candidate will never replace a `Vararg`-`Tuple` with an `NTuple`, however this discrepancy shouldn’t matter for the application. The code and testset are updated.

1 Like

The `typesplit` implementation there naively assumes the non-existence of UnionAll types, and doesn’t appear to be particularly fixable without the full power of `typeintersect`. Unlike the doc comment, that doesn’t seem to make it at all like `Base.typesplit`, which does handle other type structures. There are possibly cases where `typeintersect` cannot compute this intersection, but it seems generally uncommon (and seems much better at it than your code). For example, typeintersect should be generally capable of some of the harder cases, such as expanding constrained NTuples with simple cross-contraints:

``````julia> typeintersect(NTuple{3,Any}, Tuple{Val{N}, Vararg{Val{N},N}} where N)
Tuple{Val{2}, Val{2}, Val{2}}
``````
1 Like