`sort` ignores ordering when `by` is defined

[NymanLauri]

The sort method seems to ignore the ordering when by is defined:

Main> sort!([5,2,7], by = abs, order = Base.Order.Reverse)
3-element Array{Int64,1}:
 2
 5
 7

Main> sort!([5,2,7], by = abs, order = Base.Order.Forward)
3-element Array{Int64,1}:
 2
 5
 7

Version:

Main> versioninfo()
Julia Version 0.7.0-DEV.4690
Commit 78c7d87369* (2018-03-23 22:25 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i5-4440 CPU @ 3.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, haswell)
Environment:

The reason for this lies in ordering.jl:

abstract type Ordering end

struct ForwardOrdering <: Ordering end
struct ReverseOrdering{Fwd<:Ordering} <: Ordering
    fwd::Fwd
end

ReverseOrdering(rev::ReverseOrdering) = rev.fwd
ReverseOrdering(fwd::Fwd) where {Fwd} = ReverseOrdering{Fwd}(fwd)

const DirectOrdering = Union{ForwardOrdering,ReverseOrdering{ForwardOrdering}}

struct By{T} <: Ordering
    by::T
end

struct Lt{T} <: Ordering
    lt::T
end

lt(o::ForwardOrdering,       a, b) = isless(a,b)
lt(o::ReverseOrdering,       a, b) = lt(o.fwd,b,a)
lt(o::By,                    a, b) = isless(o.by(a),o.by(b))
lt(o::Lt,                    a, b) = o.lt(a,b)

_ord(lt::typeof(isless), by::typeof(identity), order::Ordering) = order
_ord(lt::typeof(isless), by,                   order::Ordering) = By(by)
_ord(lt,                 by::typeof(identity), order::Ordering) = Lt(lt)
_ord(lt,                 by,                   order::Ordering) = Lt((x,y)->lt(by(x),by(y)))

ord(lt, by, rev::Nothing, order::Ordering=Forward) = _ord(lt, by, order)

function ord(lt, by, rev::Bool, order::Ordering=Forward)
    o = _ord(lt, by, order)
    return rev ? ReverseOrdering(o) : o
end

Essentially the problem is that the specified ordering is not taken into account when lt and by are not default:

_ord(lt::typeof(isless), by::typeof(identity), order::Ordering) = order
_ord(lt::typeof(isless), by,                   order::Ordering) = By(by)
_ord(lt,                 by::typeof(identity), order::Ordering) = Lt(lt)
_ord(lt,                 by,                   order::Ordering) = Lt((x,y)->lt(by(x),by(y)))

In sort.jl, this ordering is then passed down to lt to determine how two elements compare to each other.

If we want to support the ordering option in addition to rev, I think ordering.jl could be implemented in the following manner:

abstract type MyOrdering end

# Some base ordering
struct BinaryOp{T} <: MyOrdering
    binary_op::T
end

# Higher order ordering: wraps args in `by(...)`
struct By{O<:MyOrdering,T} <: MyOrdering
    by::T
    binary_op::O
end

# Higher order ordering: reverses argument of binary operator
struct ReverseOrdering{O<:MyOrdering} <: MyOrdering
    binary_op::O
end

# Higher order ordering. A no-op...
struct ForwardOrdering{O<:MyOrdering} <: MyOrdering
    binary_op::O
end

(o::BinaryOp)(a, b) = o.binary_op(a, b)
(o::By)(a, b)       = o.binary_op(o.by(a), o.by(b))
(o::ReverseOrdering)(a, b)  = o.binary_op(b, a)
(o::ForwardOrdering)(a, b)  = o.binary_op(a, b)

const DefaultOp = BinaryOp(<)
const MyForward = ForwardOrdering(By(identity,BinaryOp(<)))
const MyReverse = ReverseOrdering(By(identity,BinaryOp(<)))

_ord(lt, by, order::typeof(MyForward)) = ForwardOrdering(By(by,BinaryOp(lt)))
_ord(lt, by, order::typeof(MyReverse)) = ReverseOrdering(By(by,BinaryOp(lt)))

ord(lt, by, rev::Nothing, order::MyOrdering=MyForward) = _ord(lt, by, order)

function ord(lt, by, rev::Bool, order::MyOrdering=MyForward)
    o = _ord(lt, by, order)
    return rev ? ReverseOrdering(o) : o
end

The functions in sort.jl would need to be modified so that comparison of two elements does not happen with lt but through the MyOrdering instance, for example the function call lt(o, v[i], pivot) would be replaced by o(v[i], pivot) . Some examples:

function example()
    @show BinaryOp(<)(-51, 10)
    @show By(abs, BinaryOp(<))(-51, 10)
    @show Reverse(By(abs, BinaryOp(<)))(-51, 10)
    @show Reverse(Reverse(By(abs, BinaryOp(<))))(-51, 10)
end

function example_2()
    @show ord(<,identity,false)(1,2)
    @show ord(<,abs,false)(1,2)
    @show ord(<,abs,true)(1,2)
    @show ord(<,abs,true)(1,-2)
    @show ord(<,abs,true,MyForward)(1,-2)
    @show ord(<,abs,true,MyReverse)(1,-2)
end

Main> example()
(BinaryOp(<))(-51, 10) = true
(By(abs, BinaryOp(<)))(-51, 10) = false
(Reverse(By(abs, BinaryOp(<))))(-51, 10) = true
(Reverse(Reverse(By(abs, BinaryOp(<)))))(-51, 10) = false
false

Main> example_2()
(ord(<, identity, false))(1, 2) = true
(ord(<, abs, false))(1, 2) = true
(ord(<, abs, true))(1, 2) = false
(ord(<, abs, true))(1, -2) = false
(ord(<, abs, true, MyForward))(1, -2) = false
(ord(<, abs, true, MyReverse))(1, -2) = true
true

Any ideas? Comments? Incidentally, the current implementation is not type stable and neither is this one.

[haampie]

Quick note: I think the struct ForwardOrdering is not accurate. In Base ForwardOrdering means ordering by isless (not <), and some code dispatches on that specific order (e.g. sorting a vector of Floats or searchsorted on a range). Makes more sense to have

const Forward = BinaryOp(isless) # <-- rather than DefaultOp = BinaryOp(<) 
const ForwardOrdering = typeof(Forward)

Similarly ReverseOrdering in Base currently means the order defined by (x, y) -> isless(y, x). Maybe that specific order could be renamed to BackwardOrdering, so that ReverseOrdering is just this functor-like thing that reverses the arguments. Something like this would work then:

const Backward = ReverseOrdering(Forward)
const BackwardOrdering = typeof(Backward)

[fingolfin]

The original issue is fixed in Julia 1.5.2.

[StefanKarpinski]

@fingolfin: so you think we can close this now?

[fingolfin]

Franky, I have no idea, because the only thing documented about theorder keyword argument is its name and default value. I could RTFS but as long as that's necessary one could argue there's still an issue here...

[StefanKarpinski]

It was not initially intended as a public API, but it seems to have flown the coop.

[vtjnash]

Closing as we have other issues open for documentation this properly. I think the resolution is that you specify both, but–much like you need to specify a valid total order for lt–you also need to specify a compatible definition of order given the other arguments.