I was kind of intrigued by this problem, and was curious to see if the sorting could be done completely at compile time. I’m certainly not saying that this is the right solution (and the Julia 0.6.1 compiler can almost, but not quite handle it), but I hope my attempt to torture the compiler a bit will at least amuse some people and maybe spark some discussion.

First, some setup:

```
using Base.Test
abstract type ParticleType end
struct ChargedLepton <: ParticleType end
struct Hadron <: ParticleType end
struct AntiNeutrino <: ParticleType end
```

Next, I defined a function that determines the first argument of a given type (this is inspired by StaticArrays’ `first_static`

). It returns a tuple containing the first match (or `nothing`

if there is no match), as well as all non-matches (`discards`

):

```
# start with an empty `discards` tuple:
@inline function first_type_match(::Type{T}, ts...) where T
first_type_match(T, (), ts...)
end
# not a match; add first argument to discards and recurse:
@inline function first_type_match(::Type{T}, discards::Tuple, t1, ts...) where T
first_type_match(T, tuple(discards..., t1), ts...)
end
# match: return
@inline function first_type_match(::Type{T}, discards::Tuple, t1::T, ts...) where T
(t1, tuple(discards..., ts...))
end
# no match and done processing all arguments: return
@inline function first_type_match(::Type{T}, discards::Tuple) where T
(nothing, discards)
end
```

Note: the `@inline`

s might not be completely necessary. Here is this function in action:

```
@test begin
match, discards = first_type_match(Hadron, Hadron(), ChargedLepton())
match == Hadron() && discards == (ChargedLepton(),)
end
@test begin
match, discards = first_type_match(Hadron, ChargedLepton(), Hadron(), AntiNeutrino())
match == Hadron() && discards == (ChargedLepton(), AntiNeutrino())
end
@test begin
match, discards = first_type_match(ChargedLepton, AntiNeutrino(), Hadron())
match == nothing && discards == (AntiNeutrino(), Hadron())
end
@test begin
match, discards = first_type_match(ChargedLepton)
match == nothing && discards == ()
end
```

Note that all the work is done at compile time:

```
julia> @code_warntype first_type_match(Hadron, ChargedLepton(), Hadron(), AntiNeutrino())
Variables:
#self# <optimized out>
#unused# <optimized out>
ts <optimized out>
Body:
begin
return (Hadron(), (ChargedLepton(), AntiNeutrino()))
end::Tuple{Hadron,Tuple{ChargedLepton,AntiNeutrino}}
```

I will use this function as a building block for sorting by type. To do so, we first need to specify a particle type ordering:

```
first_particle_type() = Hadron
next_particle_type(::Type{Hadron}) = ChargedLepton
next_particle_type(::Type{ChargedLepton}) = AntiNeutrino
```

Now we can define our `sort_particle_types`

function:

```
# start by looking for the first particle type with an empty results tuple
sort_particle_types(ts::ParticleType...) = _sort_particle_types(first_particle_type(), (), ts...)
const ParticleTypeTuple = Tuple{Vararg{<:ParticleType,N} where N}
# recursively build the results tuple:
@inline function _sort_particle_types(::Type{T}, result::ParticleTypeTuple, ts::ParticleType...) where T<:ParticleType
match, discards = first_type_match(T, ts...)
_sort_particle_types(handle_match(T, result, match)..., discards...)
end
# return the results tuple once all arguments have been processed:
@inline _sort_particle_types(::Type{<:ParticleType}, result::ParticleTypeTuple) = result
```

where `handle_match`

determines the next `ParticleType`

type to look for and updates the results:

```
@inline function handle_match(::Type{T}, result::ParticleTypeTuple, match::Void) where T<:ParticleType
# no match, try the next particle type
(next_particle_type(T), result)
end
@inline function handle_match(::Type{T}, result::ParticleTypeTuple, match::ParticleType) where T<:ParticleType
# reset to first particle type, append match to results
(first_particle_type(), tuple(result..., match))
end
```

Now, this almost works:

```
>julia @code_warntype sort_particle_types(ChargedLepton(), Hadron(), AntiNeutrino())
Variables:
#self# <optimized out>
ts <optimized out>
Body:
begin
return (Hadron(), ChargedLepton(), AntiNeutrino())
end::Tuple{Hadron,ChargedLepton,AntiNeutrino}
```

so the compiler has really figured out the answer already. The problem is surprisingly that you can’t actually call the function on 0.6.1, because

```
sort_particle_types(ChargedLepton(), Hadron(), AntiNeutrino())
```

somehow results in a `StackOverflowError`

in inference (despite the answer already being in the `code_warntype`

above): https://gist.github.com/tkoolen/8c3eb36aba92da194e84725c2eab18f6.

I tried this on the latest Julia master as well, and the function returns, but the `code_warntype`

shows that inference has given up:

```
julia> @code_warntype sort_particle_types(ChargedLepton(), Hadron(), AntiNeutrino())
Variables:
ts<optimized out>
Body:
begin
return $(Expr(:invoke, MethodInstance for _sort_particle_types(::Type{Hadron}, ::Tuple{Hadron,ChargedLepton}, ::AntiNeutrino, ::Vararg{AntiNeutrino,N} where N), :(Main._sort_particle_types), Hadron, (Hadron(), ChargedLepton()), :($(QuoteNode(AntiNeutrino())))))::Tuple{Vararg{ParticleType,N} where N}
end::Tuple{Vararg{ParticleType,N} where N}
```