Dispatching sort algorithm on (binary operator, map function, reverse mode)

example.jl

using Base: tail

abstract type Ord end

# Composable ordering objects

struct Op{F} <: Ord
    isless::F
end

struct Rev{O<:Ord} <: Ord
    isless::O
end

struct By{F,O<:Ord} <: Ord
    f::F
    isless::O
end

# Defaults
const Forward = Op(isless)
const Backward = Rev(Forward)
By(f) = By(f, Forward)

# Implementation of binary operators
@inline (o::Op)(a, b) = o.isless(a, b)
@inline (o::Rev)(a, b) = o.isless(b, a)
@inline (o::By)(a, b) = o.isless(o.f(a), o.f(b))

# Flattened way of writing the effective order s.t. it can be dispatched on
struct TrivialOrder{T,Op,Rev,F} <: Ord
    isless::Op
    fs::F
end

# We need to be able to get the mapped value
@inline by(o, a) = a
@inline by(o::TrivialOrder, a) = by(o.fs, a)
@inline by(o::Tuple{}, a) = a
@inline by(o::Tuple, a) = by(tail(o), first(o)(a))

# TrivialOrder's implementation of comparison
@inline (o::TrivialOrder{T,Op,true})(a, b) where {T, Op} = o.isless(by(o, a), by(o, b))
@inline (o::TrivialOrder{T,Op,false})(a, b) where {T, Op} = o.isless(by(o, b), by(o, a))

# Flatten a given order
@inline flatten(o::Op{F}, ::Type{T}) where {F,T} = TrivialOrder{T,F,false,Tuple{}}(o.isless, ())
@inline flatten(o::Union{Rev,By}, ::Type{T}) where {T} = merge(o, flatten(o.isless, T))

@inline function merge(o::By{F}, f::TrivialOrder{T,O,R,B}) where {F,T,O,R,B}
    newf = (o.f, f.fs...)
    ElT = Base._return_type(o.f, Tuple{T})
    TrivialOrder{ElT,O,R,typeof(newf)}(f.isless, newf)
end
@inline merge(o::Rev, f::TrivialOrder{T,O,R,B}) where {T,O,R,B} = TrivialOrder{T,O,!R,B}(f.isless, f.fs)
@inline merge(o::Ord, f) = o

# Now dispatch on the effective binary op + element type after the transformations
serioussort!(xs::AbstractVector{T}, o::Ord) where {T} = _serioussort!(xs, flatten(o, T))

# Example shows an implementation of sortperm basically -- it is not stable (!)
function example()
    is = collect(1:100)
    xs = randn(100)
    ord = By(abs, Rev(By(i -> @inbounds(xs[i]))))
    serioussort!(is, ord)
end

const Floats = Union{Float32,Float64}

function _serioussort!(xs::AbstractVector, o::TrivialOrder{T,typeof(isless)}) where {T<:Floats}
    println("Dispatching on ", typeof(isless), " as comparison function and inferred element type ", T)
end