Type intersection with `NTuple{len,Any}`

General Usage
, , ,
1

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
2

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