Extract unique types between two Tuples at compile time

General Usage Performance
,
1

Hello,

I have two Tuples x and y containing objects of different types. I now want to create at compile time a list containing only the unique types. I have tried this

function test2(x::T1, y::T2) where {T1 <: Tuple, T2 <: Tuple}
    all_types = (T1.parameters..., T2.parameters...)
    return unique(all_types)
end

x = (1, 2, 3 + 1im)
y = (4, 5.0)

test2(x, y)

which however returns a Vector, so the length is not known, as well as the list of the types.

Is there a way to do it without using the @generated macro?

For example, if I have two NamedTuples, the merge function does something similar to the keys, as they need to be merged.

2

This was a fun exercise. I took inspiration from your comment about merging NamedTuples and came up with the following. Not sure if it handles every case, but it works for the x and y you gave.

@inline function symbolize(T)
    if isempty(T.parameters)
        return T.name.name
    else
        params = ntuple(i -> symbolize(T.parameters[i]), length(T.parameters))
        return Symbol(T.name.name, "{", params..., "}")
    end
end

@inline function make_nt(T)
    name = (symbolize(T),)
    NamedTuple{name}(name)
end

function get_unique_types(x::T1, y::T2) where {T1 <: Tuple, T2 <: Tuple}
    nts1 = ntuple(i -> make_nt(T1.parameters[i]), length(T1.parameters))
    nts2 = ntuple(i -> make_nt(T2.parameters[i]), length(T2.parameters))
    ntc = merge(nts1..., nts2...)
    return keys(ntc)
end
`@code_warntype` output 
julia> x = (1, 2, 3 + 1im); y = (4, 5.0);

julia> get_unique_types(x, y)
(:Int64, Symbol("Complex{Int64}"), :Float64)

julia> @code_warntype get_unique_types(x, y)
MethodInstance for get_unique_types(::Tuple{Int64, Int64, Complex{Int64}}, ::Tuple{Int64, Float64})
  from get_unique_types(x::T1, y::T2) where {T1<:Tuple, T2<:Tuple} @ Main REPL[1]:15
Static Parameters
  T1 = Tuple{Int64, Int64, Complex{Int64}}
  T2 = Tuple{Int64, Float64}
Arguments
  #self#::Core.Const(Main.get_unique_types)
  x::Tuple{Int64, Int64, Complex{Int64}}
  y::Tuple{Int64, Float64}
Locals
  #3::var"#get_unique_types##2#get_unique_types##3"{Tuple{Int64, Float64}}
  #2::var"#get_unique_types##0#get_unique_types##1"{Tuple{Int64, Int64, Complex{Int64}}}
  ntc::@NamedTuple{Int64::Symbol, var"Complex{Int64}"::Symbol, Float64::Symbol}
  nts2::Tuple{@NamedTuple{Int64::Symbol}, @NamedTuple{Float64::Symbol}}
  nts1::Tuple{@NamedTuple{Int64::Symbol}, @NamedTuple{Int64::Symbol}, @NamedTuple{var"Complex{Int64}"::Symbol}}
Body::Tuple{Symbol, Symbol, Symbol}
1 ─ %1  = Main.ntuple::Core.Const(ntuple)
│   %2  = Main.:(var"#get_unique_types##0#get_unique_types##1")::Core.Const(var"#get_unique_types##0#get_unique_types##1")
│   %3  = $(Expr(:static_parameter, 1))::Core.Const(Tuple{Int64, Int64, Complex{Int64}})
│   %4  = Core.apply_type(%2, %3)::Core.Const(var"#get_unique_types##0#get_unique_types##1"{Tuple{Int64, Int64, Complex{Int64}}})
│         (#2 = %new(%4))
│   %6  = #2::Core.Const(var"#get_unique_types##0#get_unique_types##1"{Tuple{Int64, Int64, Complex{Int64}}}())
│   %7  = Main.length::Core.Const(length)
│   %8  = $(Expr(:static_parameter, 1))::Core.Const(Tuple{Int64, Int64, Complex{Int64}})
│   %9  = Base.getproperty(%8, :parameters)::Core.Const(svec(Int64, Int64, Complex{Int64}))
│   %10 = (%7)(%9)::Core.Const(3)
│         (nts1 = (%1)(%6, %10))
│   %12 = Main.ntuple::Core.Const(ntuple)
│   %13 = Main.:(var"#get_unique_types##2#get_unique_types##3")::Core.Const(var"#get_unique_types##2#get_unique_types##3")
│   %14 = $(Expr(:static_parameter, 2))::Core.Const(Tuple{Int64, Float64})
│   %15 = Core.apply_type(%13, %14)::Core.Const(var"#get_unique_types##2#get_unique_types##3"{Tuple{Int64, Float64}})
│         (#3 = %new(%15))
│   %17 = #3::Core.Const(var"#get_unique_types##2#get_unique_types##3"{Tuple{Int64, Float64}}())
│   %18 = Main.length::Core.Const(length)
│   %19 = $(Expr(:static_parameter, 2))::Core.Const(Tuple{Int64, Float64})
│   %20 = Base.getproperty(%19, :parameters)::Core.Const(svec(Int64, Float64))
│   %21 = (%18)(%20)::Core.Const(2)
│         (nts2 = (%12)(%17, %21))
│   %23 = Main.merge::Core.Const(merge)
│   %24 = nts1::Core.Const(((Int64 = :Int64,), (Int64 = :Int64,), (var"Complex{Int64}" = Symbol("Complex{Int64}"),)))
│   %25 = nts2::Core.Const(((Int64 = :Int64,), (Float64 = :Float64,)))
│         (ntc = Core._apply_iterate(Base.iterate, %23, %24, %25))
│   %27 = Main.keys::Core.Const(keys)
│   %28 = ntc::Core.Const((Int64 = :Int64, var"Complex{Int64}" = Symbol("Complex{Int64}"), Float64 = :Float64))
│   %29 = (%27)(%28)::Core.Const((:Int64, Symbol("Complex{Int64}"), :Float64))
└──       return %29

EDIT: This code outputs Symbols, not types as requested in the OP. See my later comment for slight changes to return types instead.

1 Like
3

Thanks! It works.

4

I’m glad it works! Though I just realized that the function I gave you gives you Symbols, not the types themselves. If you want the types themselves, define make_nt as:

@inline make_nt(T) = NamedTuple{(symbolize(T),)}((T,))

And then in get_unique_types:

return values(ntc)
5

for acessing the types of a tuple (or any other struct), the way to do it without using the fields of DataType is by using the function fieldtypes

julia> m = (1.0,2,"a")
(1.0, 2, "a")

julia> fieldtypes(typeof(m))
(Float64, Int64, String)
2 Likes
6

Thanks for the reminder. But using fieldtypes, and using Symbol instead of my custom symbolize (to avoid using the fields of DataType), seems to break the “at compile time” requirement of the OP. But maybe there’s another way to make it work at compile time without relying on the fields of DataType.

1 Like
7

This function with tuple recursion seems to compile to consts

function _add_el(tup, new)
    new in tup ? tup : (tup..., new)
end

function _add(tup::Tuple, tup2::Tuple)
    if length(tup2) > 1
        x, rest... = tup2
        _add(_add_el(tup, x), rest)
    elseif length(tup2) == 1
        _add_el(tup, only(tup2))
    else
        tup
    end
end

_add((Int, Float64), String)

_add((Int, Float64), (String, Int))

function f(tup1, tup2)
    types1 = map(typeof, tup1)
    types2 = map(typeof, tup2)
    init = ()
    return _add(_add(init, types1), types2)
end

x = (1, 2, 3 + 1im)
y = (4, 5.0)

f(x, y)
2 Likes
8

Looks like a perfect use case for a generated function

@generated function unique_types(a...)
    ret = Tuple(unique(a))
    return quote $ret end
end
f(tup1::Tuple, tup2::Tuple) = unique_types(tup1..., tup2...)

x = (1, 2, 3 + 1im)
y = (4, 5.0)
f(x, y)
2 Likes
9

I agree, using @generated would have been my first thought for solving this, but the OP specifically asked

Is there a way to do it without using the @generated macro?

10

If you don’t want to use @generated this is potentially a good use-case for @assume_effects:

Base.@assume_effects :foldable _funique(args::Type...) = Tuple(unique(args))
unique_types(args...) = _funique(typeof.(args)...)
f(tup1, tup2) = unique_types(tup1..., tup2...)

This basically tells the compiler that _funique is allowed to be evaluated at compile time even though the compiler would normally not allow itself to do that due to the Array allocated by unique.

1 Like
11

You can get something similar to Mason’s answer without the need to @assume_effects if you’re ok getting a Union type back:

julia> unique_types(args...) = _unique_types(Union{}, args...)
unique_types (generic function with 1 method)

julia> _unique_types(u) = u
_unique_types (generic function with 1 method)

julia> _unique_types(u, t) = Union{u, typeof(t)}
_unique_types (generic function with 2 methods)

julia> _unique_types(u, t, args...) = _unique_types(Union{u, typeof(t)}, args...)
_unique_types (generic function with 3 methods)

julia> unique_types(1, "2", 3.)
Union{Float64, Int64, String}

julia> @code_warntype unique_types(1, "2", 3.)
MethodInstance for unique_types(::Int64, ::String, ::Float64)
  from unique_types(args...) @ Main REPL[1]:1
Arguments
  #self#::Core.Const(Main.unique_types)
  args::Tuple{Int64, String, Float64}
Body::Type{Union{Float64, Int64, String}}
1 ─ %1 = Main._unique_types::Core.Const(Main._unique_types)
│   %2 = Main.Union::Core.Const(Union)
│   %3 = Core.apply_type(%2)::Core.Const(Union{})
│   %4 = Core.tuple(%3)::Core.Const((Union{},))
│   %5 = Core._apply_iterate(Base.iterate, %1, %4, args)::Core.Const(Union{Float64, Int64, String})
└──      return %5

Tuples are a good example case where recursive splatting can be ok (as long as you keep splatting fewer and fewer elements).

1 Like