Kernel.compare/2 and Comparable protocol

[Michał Muskała]

Hello everybody,

Today I’d like to address one of annoyances of working with elixir - comparing structs. It’s a problem because of two reasons:
- it’s not widely known that the regular comparison operators do not work correctly with structs
- there’s no standard way of providing custom comparison function.
This issue is especially apparent in couple libraries, most notably Ecto (with calendar types), decimal and with the new standard calendar types.

I propose adding a Kernel.compare/2 function with signature:
compare(term, term) :: :lt | :eq | :gt

I would propose following properties of the function:
- inlined implementation for built-in types, only for both arguments of the same type
- for structs the function calls the Comparable.compare/2 protocol function
- implementation for structs are allowed to return value for two different types when it makes sense
- the protocol is also implemented for built-in types
- the protocol does not fallback to Any

I’m convinced this will allow for much easier experience when comparing structs, even though the VM does not allow to extend the regular comparison operators.

Michał.

[José Valim]

Thank you for starting this discussion, Michał. I feel, however, including examples of code that could be improved by this proposal would strongly benefit the discussion. I would also like to hear a fair assessment of the downsides of such feature. A couple come to mind but I won't release spoilers. :)

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Director of R&D

Michał.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/836EAED5-CCA7-4144-A14B-E9637140A55C%40muskala.eu.
For more options, visit https://groups.google.com/d/optout.

[Peter Hamilton]

Is there any requirement for Comparable to be in elixir core? Could this be implemented as a library?

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.

To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.

[Michał Muskała]

> On 07 Aug 2016, at 22:24, José Valim <jose....@plataformatec.com.br> wrote:
>
> Thank you for starting this discussion, Michał. I feel, however, including examples of code that could be improved by this proposal would strongly benefit the discussion. I would also like to hear a fair assessment of the downsides of such feature. A couple come to mind but I won't release spoilers. :)

Code example is tricky in here, because given the type already provides a compare/2 function it wouldn’t change much, i.e.
Ecto.DateTime.compare(starts_at, ends_at) would turn into compare(starts_at, ends_at). Not a big difference. The biggest difference is discoverability of that function and making it standard across all various types.

As to downsides, there are some limitations. The biggest one is probably the fact that protocols dispatch based on just the first argument - ideally we would have a multimethod dispatching on both types - this is not available in Elixir right now (and probably it never will be). So the issue is with comparing different types. compare(Decimal.new(1), 1) would work correctly, but compare(1, Decimal.new(1)) wouldn’t. That’s why I said I would be mostly inclined to allowing this function working only across the same type.
Another issue is that this function would require some work to adapt for Enum.sort/2. The function in sort is expected to return true if arguments are in the right order, a stable implementation with compare would look like this: Enum.sort(list, &(compare(&1, &2) in [:lt, :eq])), which is a bit of a mouthful.
Finally the function wouldn’t work in guards, but that’s true of most of custom functions that are lacking natively in BEAM.

> On 07 Aug 2016, at 22:25, Peter Hamilton <petergh...@gmail.com> wrote:
>
> Is there any requirement for Comparable to be in elixir core? Could this be implemented as a library?
>

Yes. I see big benefit for that function with native calendar types that ship with elixir. Including it in core makes sense in that regard. Furthermore, standalone protocols are a mildly bad idea. We already experience some pains with that in regards to the decimal library and poison. Neither one depends on the other and there’s no canonical Poison.Encoder implementation for Decimal. Ecto has it’s own implementation and that’s mostly fine, but there are some libraries that use decimal and poison and doesn’t depend on Ecto - they define their own implementation of the protocol. This leads to issues with duplicate modules when you use such a library and ecto in the same project.

Michał.

[Peter Hamilton]

> standalone protocols are a mildly bad idea. 

I'd love for some exploration of solutions to the painpoints of protocols. That may be a separate discussion but it seems like if that's the status quo then protocols need to be revisited. That's not a knock against the current implementation of protocols, but perhaps there's a lesson to be learned and productive changes that can be made in the future.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.

To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/70019F09-3148-4031-8DFF-E674571A7F24%40muskala.eu.

[José Valim]

Finally the function wouldn’t work in guards, but that’s true of most of custom functions that are lacking natively in BEAM.

Which leads to a discussion I had with Eric some time ago about the inclusion of decimal into the standard library: if the package is not going to feel integrated with the rest of the language (like any other native type in the decimal case) then what are the benefits of including it in the language if it is going to provide the same feature set it would as a package? In other words, if won't feel as part of the language as < and >, then why shouldn't it be a package? Do we expect the majority of Elixir developers to use it? Does it considerably change the way we program in Elixir?

 

Yes. I see big benefit for that function with native calendar types that ship with elixir. Including it in core makes sense in that regard. Furthermore, standalone protocols are a mildly bad idea.

If the decision of including a protocol in standard library is because of issues for doing conflict resolution for protocols then we need to improve protocols and not add more protocols to the language. The latter solves the issue only for the protocols added as part of the language while we leave everyone else hanging.

[Paul Schoenfelder]

Just my two cents, but why would this function return atoms instead of -1, 0, 1? Then it works easily with sorting functions, and is consistent with compare implementations in other languages. 

I can say I've seen multiple people make the mistake of trying to use the comparison operators with structs in Timex, even though there is a compare function in the API. I really only see this working if the compare operators use the protocol.

Paul

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscribe@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4LyduWvoTKS6wmxrzupEPUqxNt7vdRFjWGTmk5yyc83sw%40mail.gmail.com.

[Michał Muskała]

> On 08 Aug 2016, at 03:36, Paul Schoenfelder <paulscho...@gmail.com> wrote:
>
> Just my two cents, but why would this function return atoms instead of -1, 0, 1? Then it works easily with sorting functions, and is consistent with compare implementations in other languages.

There’s no sorting function that accepts -1, 0, 1 - sorting functions in Erlang/Elixir accept a binary function that returns true if the arguments are in correct order and false otherwise. The choice of numeric values or atoms is not clear. There are languages on both sides - haskell uses ADT for Ord typeclass, which would correspond to the atoms I’ve proposed. Integers might be more familiar for people coming from imperative/OO languages.

>
> I can say I've seen multiple people make the mistake of trying to use the comparison operators with structs in Timex, even though there is a compare function in the API. I really only see this working if the compare operators use the protocol.

We probably can’t change the comparison operator, since it’s a built-in. If we change it, it wouldn’t work in guards.

>
> If the decision of including a protocol in standard library is because of issues for doing conflict resolution for protocols then we need to improve protocols and not add more protocols to the language. The latter solves the issue only for the protocols added as part of the language while we leave everyone else hanging.
>

It’s not just that. If the protocol would be a package, I would never use it when writing another package - simply in the vain of avoiding dependencies. I only see usefulness of such protocol if it’s commonly used. It’s a similar case with calendar types - they could work as a package, but that would just create another standard - I feel like it’s a perfect example of https://xkcd.com/927/

Michał.

[Wiebe-Marten Wijnja]

why not use -1, 0, 1 instead of :lt, :eq, :gt?

Saying that using atoms is the Elixir equivalent of Haskell's Ord does not make a lot of sense, I believe; Elixir does not have static types, so any agreed-upon triple of values is equally valid to represent the different possibilities of the Ord type.

I actually like using integers, mostly for the reason that these are sorted in Erlangs term order, whereas :lt: :eq, :gt are not. This has an advantage with functions like lt?, lte?, eq?, gte?, etc., which can be constructed by just using <, <=, ==, >=, >, which probably is (a little) faster than ... in [:lt, :eq] and arguably more readable. For instance, Comparable.lt? could be implemented as:

def lt?(a, b) do
  compare(a, b) < 0
end

 

Using integers also lets us do some nice tricks, like swapping gt for lt by using *-1 (see below).

Implementing sorting is exactly as inconvenient regardless of using atoms or integers for the different cases. I don't think it's that big of a deal to just do Enum.sort(collection, fn a, b -> compare(a, b) >= 0  end)

Is there any requirement for Comparable to be in elixir core? Could this be implemented as a library?

The main advantage of Comparable being in the core language, is that it is possible to create short-circuiting (non-dispatching) definitions for the built-in types, which would make it faster.

It is completely possible (with or without comparable being part of the core language) to create a behaviour that works protocol-ish but for two arguments, and stores the implementation in a module called Comparable.Protocol.FirstType.SecondType (where the type modules are placed in alphabetic order, i.e. Erlang's term order); for many things this would not make sense, but for testing for inequality, the implementation has to be the same either way, e.g:

# pseudocode
case compare(a, b) do
 -1 -> implies compare(b, a) == 1
 0 -> implies compare(b, a) == 0
 1 -> implies compare(b, a) == -1
end

so only a single definition is needed, and the other can be filled in by swapping :lt and :gt from the output of the first. Dispatching can be done by using a guard-clause which checks the order of the module names:

Comparable do

  # ... fill in non-dispatching implementations for built-in types here.

  def compare(a = %type_a{}, b = %type_b{}) when type_a <= type_b do
    Comparable.Protocol.compare(a, b)
  end

  def compare(a = %type_a{}, b = %type_b{}) do
    Comparable.Protocol.compare(a, b) * -1
  end
end

Of course, the syntax to add an implementation of the comparison protocol is something we still have to figure out, but that is mostly a syntactic thing; Either we amend the current protocol implementation to allow something like passing a two-element list to the `for: ` field of defimpl, or we make it a whole different beast altogether.

The main hurdle that remains is who is in charge of an implementation of Comparable. In the case of built-in types, this would be the core language; not an issue. In the case of comparing a custom struct against a core type (such as Decimal against Integer), it is the library's responsibility.

However, what happens when we want to compare two custom structs between two libraries? Say, %Decimal{} vs %Ratio{} ? Where should the two-argument protocol be defined? How do we make sure that not both libraries attempt to do so, resulting in errors because the protocol module would be overridden? 

I think the best way would be to put such definitions inside an auxiliary library, I think; Just like how a JSON (Poison)-implementation of Decimal would be best put in its own library, to prevent dependency-issues like these (which Michał mentioned above as well). What do you think?

[Dmitry Belyaev]

Integers completely hide the meaning of the comparison result. You can do those simple lt? as equality check:

compare(a, b) != :gt

Also ordering and equality are not the same in general. I think struct equality needs to be solved first but the discussion went in the wrong direction.

On 9 August 2016 00:52:10 GMT+10:00, Wiebe-Marten Wijnja <w.m.w...@panache-it.com> wrote:
>
>>
>> why not use *-1, 0, 1* instead of* :lt, :eq, :gt*?

>>
>
>Saying that using atoms is the Elixir equivalent of Haskell's Ord does
>not
>make a lot of sense, I believe; Elixir does not have static types, so
>any
>agreed-upon triple of values is equally valid to represent the
>different
>possibilities of the Ord type.
>
>I actually like using integers, mostly for the reason that these are
>sorted

>in Erlangs term order, whereas *:lt: :eq, :gt* are not. This has an
>advantage with functions like *lt?, lte?, eq?, gte?*, etc., which can
>be
>constructed by just using *<, <=, ==, >=, >, *which probably is (a
>little)
>faster than ... *in [:lt, :eq] *and arguably more readable. For

>instance,
>Comparable.lt? could be implemented as:
>
>def lt?(a, b) do
> compare(a, b) < 0
>end
>

>Using integers also lets us do some nice tricks, like swapping *gt* for
>*lt* by

>using *-1 (see below).
>
>Implementing sorting is exactly as inconvenient regardless of using
>atoms
>or integers for the different cases. I don't think it's that big of a
>deal

>to just do *Enum.sort(collection, fn a, b -> compare(a, b) >= 0 end)*

><https://elixirforum.com/t/how-to-manage-conflicts-with-duplicate-dependencies-the-same-module-gets-defined-twice/1016/5>

>(which
>Michał mentioned above as well). What do you think?

--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

[Wiebe-Marten Wijnja]

I have taken some time to create an experimental module that shows how this might work in practice: https://github.com/Qqwy/elixir_experimental_comparable 

I am very interested to hear the things about this you like/dislike. :-)

Have a wonderful day,

~Wiebe-Marten/Qqwy

[Wiebe-Marten Wijnja]

I discussed with Thomas Depierre (@di4na) today about this, and he convinced me that atoms are indeed more explicit than integers, because during debugging something that crashed, instead of seeing 'a number' as result of the comparison function, you see 'a name' which is self-describing.

Instead of going with :lt, :eq and :gt, which do not follow Erlang's term ordering, I came up with using :<, := and :>, which do, and are also the mathematical symbols used when describing inequality.
The experimental example implementation I posted before has been updated to reflect this change.

On Sunday, August 7, 2016 at 10:13:45 PM UTC+2, Michał Muskała wrote:

[Wiebe-Marten Wijnja]

I am back after a week of vacation.

A week ago, I discussed this in the Internet Relay Chat group with Jose Valim, Ben Wilson and Michał Muskała.

The conclusion was that the approach I made to defining a Comparable multiprotocol worked well, but would mean n(n+1)/2 Modules being created, if there are n custom types that all want to be compared to each other (including themselves). This is the sequence of triangular numbers; If we have a single type that compares to itself, we'd need only the 1 implementation. If we have two types, we would need the implementation of comparing each of these types to themselves, as well as the comparison between them: 3. For three types, we'd need 6 implementations, for four types 10, etc.

Now while comparing all built-in Elixir types with themselves can happen without any new comparison-implementations (as Erlang's built-in comparisons work fine for this), this does mean that, when using custom data types, quite a few modules might be added. The only example I could think of was between four types of things (comparing integers, floats, Decimals and Rationals -- two of which are actually built in types), there might be cases where there are more types that want to be comparable.

If I remember correctly, the amount of modules that is being created was something that Jose and Michał disliked, and it sounded to me like it was some kind of deal-breaker that made this solution 'unsuitable'. 

As far as I can see, however, there is no way to reduce the amount of comparison-implementations, because the sequence of triangular numbers simply describes the total of amount of nodes in a fully-connected (undirected) graph.

As modules are the atomic compile-able unit on the BEAM, it makes the most sense to use one per comparison-implementation. Of course it is possible to do fancy stuff similar to protocol consolidation and smash multiple modules together, but I don't see what problem is solved by that.

So, I would like to know: 

- Why is it a 'bad' thing to define multiple modules?

- Are there any other things about this implementation that you do not like, and why?

Have a nice evening,

~Wiebe-Marten Wijnja

[OvermindDL1]

Quickly read over, but why not just enforce that comparables must compare the same types only.  So you could do `compare(some_date, Timex.now |> Time.add(4, :days))` or so, helper functions make that simple and keeps things explicit.

And yes, atoms should definitely be used, that is the erlangy way as well.

[Ben Wilson]

Because half the point of the comparable protocol is making it easy to compare numbers generically, where "numbers" can be any of integer, float, decimal, rational.

[OvermindDL1]

To compare any type of number to any type of number?  Or to compare any type of number to another of the same type?  Also I can see many usages of compare beyond number comparisons too.

If the first, I'm unsure what sense it is to compare, say, a decimal to a Timex date?

[Wiebe-Marten Wijnja]

The idea is to be able to create application-specific comparisons between data types, where these comparisons make sense. Some examples:

- Being able to compare Integers with Floats, Arbitrary precision Decimals (which are implemented as %Decimal{} structs by the 'decimal' package) and Rational numbers (which are implemented as %Ratio{} structs by the 'ratio' package).

- Being able to compare different Vector or Matrix types in a similar way.

- Being able to compare datetimes in different storage formats or calendars with each other.

- If your application works with %Bike{}, %Car{} and %Truck{} structs, it might make sense to always have the ordering %Bike{} < %Car{} < %Truck{}, and have some other kind of criteria when comparing one %Bike{} with the other (like frame height) or one %Car{} with the other (like motor capacity).

- Being able to compare elements in any other imaginable partially ordered set, where elements of the poset might be of different types. 

Comparing e.g. a Decimal with a Timex date makes no sense in most contexts. (If you want, you could go ahead and do something like letting a Timex date be larger iff it is an odd date. It is nonsensical, but possible). Therefore, an implementation of the multiprotocol that would be used to compare data types of these kinds would not be made.

Does that answer your question?

[José Valim]

Given the examples below, maybe it would be better to provide protocols for each of those cases. The protocol would convert those data types to an intermediate representation that would be easy to compare on.

--

You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscribe@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/b31aec7d-6bb0-4afa-ae88-9adfa6aa4537%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

[OvermindDL1]

On Monday, August 29, 2016 at 2:26:41 PM UTC-6, Wiebe-Marten Wijnja wrote:

The idea is to be able to create application-specific comparisons between data types, where these comparisons make sense.

Hmm, being able to compare disjoint types seems potentially painful and most likely incurring a significant overhead compared to just doing it manually...  I'm guessing that is where the module explosion talked of before came in to play.  It sounds like needing to create a multi-method dispatcher in Elixir, and if so the best you could get (without knowing all types absolutely at compile-time) would be log(N) runtime, which is not too bad...

You could potentially sneak in some tricks though.  If you use something like protocols (though something new, not protocol) to generate a call tree in a single module, a single entrance function that matches based on both of the types (properly ordered so the beam can efficiently match well) would get it down to log(n).  Hmm, although if you have a *lot* of potential matches (and I mean a **LOT**) then you could dispatch into a map and that 'might' be faster (though honestly I would not bet on it).  This would require a post-compile step like protocols do though (is there a pattern to do those kind of things with elixir or are protocols just 'special'?).  For normal macro's the best you could really get is to manually specify everything in a single file in your base project, just import the other modules that define matchers, and have a macro build up the same call tree.  Easy enough to do but does require the end-user to import all other possible modules compare implementations into it so the macro can build the call tree, which can be easy to forget something, but good enough for an initial test implementation.

With that you would only have 1 module necessary (with an additional 1 for each you import, but those could just be function calls onto some base module for each type so that is effectively free).  But the macro would just generate something like:

```elixir

# Example structs
defmodule Bike do
  defstruct gears: 5
end

defmodule Car do
  defstruct top_speed: 80
end

defmodule Truck do
  defstruct wheels: 4
  def compare(%{wheels: wheels0}, %{wheels: wheels1}), do: Comparable.compare
end

# An example of what a macro could generate given some information that describes things:
defmodule Comparable do
  def compare(t, t), do: :eq
  # Could generalize this call to something like:
  # def compare(%{__struct__: type}=t0, %{__struct__: type}=t1), do: type.compare(t0, t1)
  # However that catches structs that do not support a compare and has a speed overhead due to dynamic dispatch, so I would not recommend it
  def compare(%Bike{gears: gears0}, %Bike{gears: gears1}), do: compare(gears0, gears1)
  def compare(%Bike{}, %Car{}), do: :lt
  def compare(%Bike{}, %Truck{}), do: :lt
  def compare(%Car{top_speed: top_speed0}, %Car{top_speed: top_speed1}), do: compare(top_speed0, top_speed1)
  def compare(%Car{}, %Bike{}), do: :gt
  def compare(%Car{}, %Truck{}), do: :lt
  def compare(%Truck{wheels: wheels0}, %Truck{wheels: wheels1}), do: compare(wheels0, wheels1)
  def compare(%Truck{}, %Bike{}), do: :gt
  def compare(%Truck{}, %Car{}), do: :gt
  def compare(%{__struct__: _t0}, %{__struct__: _t1}, do: raise MatchError(blah)
  def compare(t0, t1), do: if(t0<t1, then: :lt, else: if(t0>t1, do: :gt, else: if(t0 == t1, do: :eq, else: raise MatchError(blah))))
end

```

That should be quite easily optimizable by the beam and be quite efficient, even with large match sets (log(n) specifically).

On Monday, August 29, 2016 at 2:58:15 PM UTC-6, José Valim wrote:

Given the examples below, maybe it would be better to provide protocols for each of those cases. The protocol would convert those data types to an intermediate representation that would be easy to compare on.

 

This could indeed be faster, however you'd have to get everything to agree on a single representation (a special tuple format perhaps? but then how would that rank with other tuples?).

[OvermindDL1]

Do note, in my example the lines like:

def compare(%Bike{gears: gears0}, %Bike{gears: gears1}), do: compare(gears0, gears1)

The `compare(gears0, gears1)` part is writer-defined, it could call into a module function, it could do an inline compare like the above is doing, whatever is appropriate for the type.

[José Valim]

This could indeed be faster, however you'd have to get everything to agree on a single representation (a special tuple format perhaps? but then how would that rank with other tuples?).   

You don't have to agree on a format though. Imagine Decimal defines its own format and Rational defines another, as long as at some point you implement each other protocols, anywhere, it will work just fine. That's the beauty of protocols after all! In the worst scenario, it will degenerate to the case we are talking about right now: (n * (n - 1) / 2) implementations?

[Wiebe-Marten Wijnja]

What we miss when doing a pre-compile step, is things like:

{A} should be comparable with {B}, {B} should be comparable with {C}, but {A} and {C} cannot be compared in a meaningful way.

I cannot think of a practical example right now, but I think it is a valid problem.

Also, when a third data type needs to be added to an existing intermediate representation, how can this be done? There will be cases in which this existing intermediate representation is no longer valid, but you're unable to change the protocol implementations of those other types, so you're stuck. 

I also think that there are many cases in which it might be impossible to come up with a proper intermediate format. We have both Enum.sort_by (which uses a Schwarzian Transform, i.e. it first creates an intermediate representation for all data elements and then sorts based on these) and the normal Enum.sort. Although it usually is faster, there are cases where it is impractical or impossible to use Enum.sort_by.

An example: What about cases like Rock, Paper Scissors? Rock < Paper, Paper < Scissors, Scissors < Rock? Although there is no complete order for these data structures, we do want to be able to compare individual pairs.

Another nice edge case that would go completely wrong with an intermediate-representation approach, would be NaN, which is unequal to everything else, including itself.

So, I think it is paramount to create a multiprotocol or multimethod-like approach that works on the relationship or combination of the two types being compared. On an edge of the graph, rather than on a node like normal protocols do. After all, a comparison is something that is about the relationship between two things. You cannot compare a single thing.

On Sunday, August 7, 2016 at 10:13:45 PM UTC+2, Michał Muskała wrote:

[OvermindDL1]

On Monday, August 29, 2016 at 3:14:04 PM UTC-6, José Valim wrote:

This could indeed be faster, however you'd have to get everything to agree on a single representation (a special tuple format perhaps? but then how would that rank with other tuples?).   

You don't have to agree on a format though. Imagine Decimal defines its own format and Rational defines another, as long as at some point you implement each other protocols, anywhere, it will work just fine. That's the beauty of protocols after all! In the worst scenario, it will degenerate to the case we are talking about right now: (n * (n - 1) / 2) implementations?

They certainly could do that yep, but the code to compare their formats still has to be somewhere, all my suggestion does is state where that somewhere should be (a prolog'y style relationship description, which erlang is awesome at and well optimized for), with only a single module (but potentially a lot of matches, which if organized well will be *very* efficient, log(N)).  :-)

On Monday, August 29, 2016 at 3:35:51 PM UTC-6, Wiebe-Marten Wijnja wrote:

What we miss when doing a pre-compile step, is things like:

{A} should be comparable with {B}, {B} should be comparable with {C}, but {A} and {C} cannot be compared in a meaningful way.

I cannot think of a practical example right now, but I think it is a valid problem.

My suggested method does support this (it would throw some error if {A} and {C} were compared).

On Monday, August 29, 2016 at 3:35:51 PM UTC-6, Wiebe-Marten Wijnja wrote: 

Also, when a third data type needs to be added to an existing intermediate representation, how can this be done? There will be cases in which this existing intermediate representation is no longer valid, but you're unable to change the protocol implementations of those other types, so you're stuck.

Yeah just like with protocols, no real good way to update it without hot-code swapping. 

On Monday, August 29, 2016 at 3:35:51 PM UTC-6, Wiebe-Marten Wijnja wrote:

I also think that there are many cases in which it might be impossible to come up with a proper intermediate format. We have both Enum.sort_by (which uses a Schwarzian Transform, i.e. it first creates an intermediate representation for all data elements and then sorts based on these) and the normal Enum.sort. Although it usually is faster, there are cases where it is impractical or impossible to use Enum.sort_by.

An example: What about cases like Rock, Paper Scissors? Rock < Paper, Paper < Scissors, Scissors < Rock? Although there is no complete order for these data structures, we do want to be able to compare individual pairs.

Which my suggestion also supports.  Would be an interesting trouble for a fully typed system though...

On Monday, August 29, 2016 at 3:35:51 PM UTC-6, Wiebe-Marten Wijnja wrote:

Another nice edge case that would go completely wrong with an intermediate-representation approach, would be NaN, which is unequal to everything else, including itself.

Which my suggestion could also support (perhaps by throwing an error, or return a :non_comparable atom or something, whatever was wanted).

On Monday, August 29, 2016 at 3:35:51 PM UTC-6, Wiebe-Marten Wijnja wrote:

So, I think it is paramount to create a multiprotocol or multimethod-like approach that works on the relationship or combination of the two types being compared. On an edge of the graph, rather than on a node like normal protocols do. After all, a comparison is something that is about the relationship between two things. You cannot compare a single thing.

My suggestion follow a very prology way, which is precisely relationship descriptions (which erlang is awesome at).

[Wiebe-Marten Wijnja]

Have you read the code of the implementation that was talked about earlier in this topic? It works in a way that is similar to the solution you propose, with the difference that dispatching does not work based on a pattern match, but based on the extracted struct names (and for the built-in types, guard-clause matches).

I do not think your solution (e.g. 'some macro' that outputs the code snippet you outlined)  is able to work across projects, where Project A defines a data type, Project B defines a data type, Project C defines a frequent way of comparing A and B, and A, B and C are used by some person in his personal project D, together with another custom data type D that should be able to compare to both A and B as well.

The only way for all of these data types to work together, is to make something that can be extended after its original definition was made. It is not possible to 'add more clauses to a function' after the module it is contained in is closed and compiled. This is the fundamental problem with and the fundamental difference in the solution you have proposed.

[OvermindDL1]

Indeed, that is why I stated it would have to have some resolved step.  :-)

Like I mentioned earlier:

You could potentially sneak in some tricks though.  If you use something like protocols (though something new, not protocol) to generate a call tree in a single module, a single entrance function that matches based on both of the types (properly ordered so the beam can efficiently match well) would get it down to log(n).  Hmm, although if you have a *lot* of potential matches (and I mean a **LOT**) then you could dispatch into a map and that 'might' be faster (though honestly I would not bet on it).  This would require a post-compile step like protocols do though (is there a pattern to do those kind of things with elixir or are protocols just 'special'?).  For normal macro's the best you could really get is to manually specify everything in a single file in your base project, just import the other modules that define matchers, and have a macro build up the same call tree.

Thus unless an after-compile step is done a work-around for now is to be more explicit, perhaps something like this:

```elixir

# Let's define our own things from earlier:
defcompare Car.Compare do # Whatever namespace you want, let's just put each in their own .Compare
  defcompare (%Car{top_speed: top_speed0}, %Car{top_speed: top_speed1}), do: compare(top_speed0, top_speed1)
  defcompare (%Car{}, %Bike{}), do: :gt

  defcompare (%Car{}, %Truck{}), do: :lt

end

defcompare Bike.Compare do
  defcompare (%Bike{gears: gears0}, %Bike{gears: gears1}), do: compare(gears0, gears1)
  defcompare (%Bike{}, %Car{}), do: :lt

  defcompare (%Bike{}, %Truck{}), do: :lt

end

# Let's define trucks inline below, just because

defcompare Compare do # Let's make a top-level Compare (no one should do this unless in a final project, non-library
  # Bring in other libraries if they have definitions, otherwise define them all inline
  defcompare Timex.Compare
  defcompare OtherStuff.Compare
  defcompare Car.Compare
  defcompare Bike.Compare

  # Truck inline, just for an example:
  defcompare (%Truck{wheels: wheels0}, %Truck{wheels: wheels1}), do: compare(wheels0, wheels1)
  defcompare (%Truck{}, %Bike{}), do: :gt

  defcompare (%Truck{}, %Car{}), do: :gt

end

```

At which point you would have a `Car.Compare.compare/2`, `Bike.Compare.compare/2`, and a `Compare.compare/2` or whatever it should be named as.  Each `defcompare` at the module-level defines a public `compare/2` function in addition to something like a `__comparedefs__/0` method that returns, oh, say a useful AST that can be used in embedded it elsewhere.  Have the defcompare module-level macro parse over all its internal defcompare calls, if it is a module then import its ast and hold on to it, if it is like a function definition (without the name) then add those AST's to it as well, and finally merge those all together ordering by the first argument, then the second, and the when tests last for general efficiency (better ways of doing it but this will work best in the majority of cases).

It is unlike the prior example code in that it would move the final 'Compare' thing to the user of which they should have their final version be named something uniform, like `Compare` that everything else could call, only the final parent application of a project should define a `Compare`, no library or so.  It is an ugly limitation but it is very efficient and that limitation is entirely removed if a post-process compile step like protocols is added, and someone could indeed write such a compiler as well, just have to add it to a main projects mix.exs compilers.

[Robert Virding]

I have missed most of the discussion but it feels strange that a function in Kernel, Kernel.compare/2, results in calls to a protocol. For me Kernel feels like being at the very base and should not call anything outside it, irrespective of whether it is part of elixir core or not.

Robert

[Michał Muskała]

> On 31 Aug 2016, at 01:57, Robert Virding <rvir...@gmail.com> wrote:
>
> I have missed most of the discussion but it feels strange that a function in Kernel, Kernel.compare/2, results in calls to a protocol. For me Kernel feels like being at the very base and should not call anything outside it, irrespective of whether it is part of elixir core or not.
>
> Robert

While I understand this sentiment, there are already a lot of functions in Kernel calling protocols - inspect/2 with the Inspect protocol, to_string/1 with String.Chars protocol, to_charlist/1 with List.Chars, etc. Having a compare/2 that calls Comparable protocol seems like a good fit.

Michał.

[Wiebe-Marten Wijnja]

Two days ago I talked with OverminDL1 because I had trouble to understand exactly what his implementation was trying to do.

Now I understand, and I find it a very interesting idea. It would solve the 'too many modules' problem. (Although I still don't know why this is a problem). It would also dispatch faster, because no dynamic dispatching during calls to `compare?` would be necessary.

His idea is basically to recompile the `Compare` module every time a new comparison is defined, by taking its old AST (which could be provided by a function on the current compiled Compare module), and adding in a new `compare`-clause to handle the new comparison case. This means that most work is performed during the creation of a compare-implementation(of which there probably are relatively few), and subsequent calls to `compare` (of which there probably are many) are thus more efficient.

OverminDL1 further had the idea to allow multiple modules with such structure(i.e. extendable in the same way, but filled with different comparison implementations) to exist side-by-side, but I don't think that is something we would need. Maybe if we ever want full-blown multimethod dispatching in Elixir, but not for Comparable. KISS, YAGNI, etc.

[Wiebe-Marten Wijnja]

*brushes dust off of topic*

We are now a few months further, but I believe that a standardized method of comparing datatypes still is a relevant addition to the language.

What would be the best approach to go from here?

Some possibilities:

- More discussion here on the current implementation idea that OvermindDL1 and me came up with. Major unsolved 'problem' might be how to integrate it more with the rest of the Elixir language, as it is basically does something similar to protocols, but then for a combination of two datatypes (in no particular order, as comparison is symmetric (or in proper mathematical terms, converse)), which is similar but different from what already exists in the language.

- Maybe ask the larger group of people on the Elixirforum about their opinions on this, although this might lead to bike-shedding.

[José Valim]

We should continue the discussion here and include the implementation you have so far. I believe implementation wise, the two main questions were:

1. Should it only compare structs of the same kind

2. Or should it compare across types. If comparing across types, how would the protocol dispatch work. Should we sort both elements and dispatch the first as first?

Note that Date.compare, Time.compare, and friends changed on Elixir master and are now able to compare across types. It does a field-based comparison instead of a struct-based comparison. For example, Date.compare/2 can compare any type that contains the fields year, month and day.

When it comes to adding it to Elixir, the main drawback was that we didn't agree it added enough to the language to warrant its inclusion in Elixir. In particular, if the feature feels detached from Elixir overall, i.e. it is just a new function+protocol that doesn't actually integrate with Elixir features, such as guards, then it is probably best to leave it as a library. Especially because it may affect future decisions in the language.

For example, imagine we can access map fields or write case expressions in guards. Would that allow us to write a guard-able compare expression? How that would affect the compare implementation?

Those are the same reasons why we decided to not include Decimal as part of the standard library, it's why we don't provide an Array/Vector/Queue, etc. If it is limited in scope it is probably best to leave it apart so we still have the option to provide something truly integrated later on.

[Wiebe-Marten Wijnja]

1. Should it only compare structs of the same kind:

I believe that when only comparisons between the same kind of data type (structs or built-in) are needed, a MyDatatype.compare function would be enough, which would mean that the core language does not need to be changed.

However:

2. Or should it compare across types.

I think that this is much more useful. Some examples:

- Comparisons between different kinds of dates and times, as is already the case right now.

- Comparisons between different kinds of numeric data types (built-in integers, built-in floats, decimals, rationals, etc)

- Comparisons between different kinds of data types representing parts of a hierarchy. (An example: Chain of command)

Of course, it is possible 'fake' some of these behaviours by wrapping the different types in a single struct, and define a single-type comparison for that one. (For instance: Instead of a General, Colonel and Sergeant struct, have a single 'Soldier' struct that contains details about rank in another way.) But this means that when comparing two data types, both first need to be wrapped, so I think this is not desirable.

how would the protocol dispatch work. Should we sort both elements and dispatch the first as first?

A comparison (possibly across types) is an operation working on an ordered pair of datatypes.

To make the dispatching underwater work, we could do one of the following:

I see two possibilities:

a) At runtime, sort the element module names (for built-in types, these are the 'fake' module names Integer, Float, etc. that are also used to define `defprotocol` and friends underwater) and dispatch on the first.

b) At compiletime, look at what way around the comparison is defined, and automatically define the other way around as its converse.

Advantage of a) is smaller code size, at the drawback of slower execution. b) has twice the code size, but is probably faster.

For the user defining the custom comparison implementation this does not really matter. 

What does matter, is that for the end user this is a 'protocol implementation' working with two datatypes instead of one. This means that, in one way or other, a way to specify this kind of 'protocol' implementation needs to be possible. Probably the easiest way (which is included in the example implementation that I constructed together with @OpenmindDL1) would be to add a macro like `defcomparable FirstType SecondType do ... end` where there _has_ to be an implementation (using one or multiple clauses) of a function named 'compare'.

There might be other ways  to do this. If someone has another idea, please do tell.

One possibility might be something akin to Clojure's multimethod approach (basically generic 'Protocol' dispatching but possibly on other or multiple arguments instead of only the first) but this introduces a whole layer of additional complexity, which I think should best be avoided in the spirit of KISS.

Note that Date.compare, Time.compare, and friends changed on Elixir master and are now able to compare across types. It does a field-based comparison instead of a struct-based comparison. For example, Date.compare/2 can compare any type that contains the fields year, month and day.

I just looked at the source of this because I was curious how it was implemented. Maybe it is important to note that for Date, it is also required that the `calendar` key is set to match `Calendar.Iso`, and 'any type' means 'any custom type built on top of a map'.

It is great that these comparison functions have been added. What it does not solve (and that is something this proposal might change) is what should happen when the second date is from a different calendar.

The field-based lookup is definitely better than a structname-based lookup, but this will only work if the different kind of data structures happen to use the same names for the same values. This is very similar to 'duck typing' in a way. For instance, I could make a %Duration{hours:, minutes: seconds:} struct. It would be possible to use `Time.compare(myDuration)` but of course this is a nonsensical calculation.

Another problem would be that the system breaks down if we have a cyclic relationship: Take Rock, Paper, Scissors. Regardless of if they are part of the same type or different types, we want Rock to beat (be greater than) Scissors, Paper to beat Rock, and Scissors to beat Paper. If the only possibility would be to specify some fields that are transformed into a tuple which is then compared using Erlang's built-in term ordering, we are stuck.

Or what if we want to compare two things that can only be compared once a complicated calculation is performed using the data that is stored inside the struct? A struct might contain only a filename, but represent the file itself.

I think a better approach would be to allow the specification of a comparison implementation as one or multiple function clauses of the `compare` function.

This indeed has the implication that it will be impossible to use `compare` in guards (even if map-field access becomes possible), but I believe that this freedom is necessary, because of the restrictions outlined above. 

[OvermindDL1]

A few notes.  :-)

At:  https://github.com/Qqwy/elixir_experimental_comparable/blob/master/lib/comparable.ex#L27-L37

Shouldn't this:

```elixir

	defcomparison(Integer, RomanNumeral) do
	def compare(int, %RomanNumeral{num: num}) when num < int, do: :<
	def compare(int, %RomanNumeral{num: num}) when num > int, do: :>
	def compare(int, %RomanNumeral{}) , do: :=
	end

```

Actually be something like:

```elixir

	defcomparison(Integer, RomanNumeral) do
	def compare(int, %RomanNumeral{num: num}), do: Comparable.compare(int, num)
	end

```

Even for primitive types it can be a bad idea not to delegate the compare function (the compiler can optimize it or so, especially with macros).  What if someone stuff something that is not an integer in the RomanNumeral somehow, they would then report as equal even when not.  That brings up the thing, maybe it should be defined as:

```elixir

	defcomparison(Integer, %RomanNumeral{num: Integer}) do
	def compare(int, %RomanNumeral{num: num}), do: Comparable.compare(int, num)
	end

```

The defcomparison line itself changed to be explicit as to what is accepted (which can be performed via a match/when internally).  Instead of having automatic naming for things like Integer, you could also do this:

```elixir

	defcomparison(int, %RomanNumeral{num: num}) when is_int(int) and is_int(num) do
	def compare(int, %RomanNumeral{num: num}), do: Comparable.compare(int, num)
	end

```

And considering that, maybe instead just entirely shrink it down to:

```elixir

	defcomparison(int, %RomanNumeral{num: num}) when is_int(int) and is_int(num) do
	Comparable.compare(int, num)
	end

```

I.E., make the `defcomparison` call itself define the function, of which you could put multiple:

```elixir

	defcomparison(int, %RomanNumeral{num: num}) when is_int(int) and is_int(num) do
	Comparable.compare(int, num)
	end defcomparison(float, %RomanNumeral{num: num}) when is_float(float) and is_int(num) do Comparable.compare(float, num) end

```

Although in this simple case you could simplify it down to just:

```elixir

	defcomparison(v, %RomanNumeral{num: num}) when is_int(num) do
	Comparable.compare(v, num)
	end

```

This states that %RomanNumerals must always hold an integer, but you can compare anything to the integer that you could normally compare to an integer (whether another integer, float, some custom type, etc...).

But the above latest syntax simplifies it, you could put multiple defcomparisons in a row like normal function heads (the 'use Comparable' declaration in the module can do the combining and optimizing work), you use normal Elixir syntax to deconstruct the types and put on when conditions, *and* you could potentially restrict the syntax to not allow costly calls so you could use compares in `when`'s, perhaps something as simple as like:

```elixir

	defcomparison(v, %RomanNumeral{num: num}) when is_int(num) and Comparable.compare(v, num)

```

That would restrict the ability to do costly computations (like the loading a file mentioned in the below post), but does allow `when` usage.  Honestly though the one just above that is probably what I'd go with, it allows complex usage (like loading a file), if someone wants to match in heads they can always call it then pass to another defp head matchers or a case expression anyway.

Also, https://github.com/expede/type_class is always an interesting idea to bake in to Elixir, and could handle this case too (an `Elixir.Ord` typeclass or so? plus the optional fuzzy testing at compile-time to ensure the typeclass is correct for the implemented types).  ^.^

/me just had coffee so may not be awake enough for this to make sense yet.

[OvermindDL1]

Just playing around with a possible typeclass-style usage:

```elixir

defclass Kernel.Eq do
  where do
    @operator == # Assuming there is a way to define an operator or so to call the next function, otherwise ignore lines like @operator
    eq?(any, any) :: boolean()
  end

  defproperty equals_self(e) do
    true == eq?(e, e)
  end
end


defclass Kernel.Ord do
  extend Kernel.Eq

  where do
    compare(any, any) :: boolean()
  end

  defproperty compare_test(l, r) do
    compare(l, r) == case compare(r, l) do
      :< -> :>
      :> -> :<
      := -> :=
    end
  end

  @operator ==
  @spec eq?(any, any) :: boolean
  def eq?(l, r), do: compare(l, r) == := # Implement Kernel.Eq's call

  @operator <
  @spec lt?(any, any) :: boolean
  def lt?(l, r), do: compare(l, r) == :<

  @operator <=
  @spec le?(any, any) :: boolean
  def le?(l, r), do: compare(l, r) in [:<, :=]

  @operator >
  @spec gt?(any, any) :: boolean
  def gt?(l, r), do: compare(l, r) == :>

  @operator >=
  @spec ge?(any, any) :: boolean
  def ge?(l, r), do: compare(l, r) in [:>, :=]

  # Etc... whatever other things you want to implement on this
end


# Some implementation!  I changed the syntax here to be more generically useful
definstance Kernel.Ord(l, r) when is_int(l) and is_int(r) do
  def compare(l, r) do
    cond do
      l<r -> :<
      l>r -> :>
      l===r -> :=
    end
end
definstance Kernel.Ord(l, r) when is_float(l) and is_float(r) do
  def compare(l, r) do
    cond do
      l<r -> :<
      l>r -> :>
      l===r -> :=
    end
end
definstance Kernel.Ord(l, r) when is_int(l) and is_float(r) do
  def compare(l, r) do
    cond do
      l<r -> :<
      l>r -> :>
      l==r -> :=
    end
end
definstance Kernel.Ord(l, r) when is_float(l) and is_int(r) do
  defdelegate compare(l, r), to: Kernel.Ord(r, l)
end
# Thought honestly for basic types you'd probably just have a single Kernel.Ord instance
# that tests for any basic type and compares appropriately, like via erlang term ordering
# for everything except `is_struct`'s.  Maybe like this:
definstance Kernel.Ord(l, r) when not is_struct(l) and not is_struct(r) do
  def compare(l, r) do # Default to erlang term ordering for all non-struct types
    cond do
      l<r -> :<
      l>r -> :>
      l==r -> := # What to do about float/int comparisons by default, leave it loose like `==`, or tight like `===`?
    end
end

# A custom type
defmodule MyDate do
  defstruct year: 0, month: 0, day: 0
end
# Lets support comparing our date with any map/struct that has year/month/day keys!
definstance Kernel.Ord(%MyDate{}, %{year: _, month: _, day: _}) when  do
  def compare(d0, d1) do
    # delegate to the list compare because I'm lazy
    Kernel.Ord.compare([d0.year, d0.month, d0.day], [d1.year, d1.month, d1.day])
  end
end
# And let's support both orders
definstance Kernel.Ord(%{year: _, month: _, day: _}, %MyDate{}) when  do
  def compare(d0, d1), do: Kernel.Ord.compare(d1, d0)
end

```

Or something like that...

```elixir

<table class="highlight tab-size js-file-line-container" data-tab-size="8" style="border-collapse: collapse; box-sizing: border-box; tab-size: 8; font-family:

[Wiebe-Marten Wijnja]

I've been thinking about this the last couple of days.

Maybe we were too quick to jump at a single solution. Let's take a step back and reassess the problem:

# The Problems

(Taken from Michał's post)

1. It is not widely known that the regular comparison operators do not work correctly with structs.

2. There is no standardized way to provide a custom comparison function.

(Additions throughout the thread)

3. There is no way to compare different kinds of structs(/different datatypes in general) with each other.

# Inspecting the problems in more detail

1) seems to be mostly a case of education (or lack thereof). We might be able to make it more clear (in e.g. the documentation) that the built-in operators do not work properly for structs. 

2) is directly related to this; it is far easier to educate people if we can not only say "Don't do X" but also are able to say  "Do Y instead".

In the meantime, since this topic was started, semi-standardized variants of 2) have been constructed, both in libraries and in Elixir Core, such as `Decimal.compare/2`, `Decimal.cmp/2` and `DateTime.compare/2`. Each of these however has slightly different behaviour in how they work, which hints at a language-wide standardized way being a good idea. Also, a built-in `compare` function that dispatches properly is easier to find in the documentation (and could be pointed to from other parts of Elixir's core documentation).

This however still leaves 3) open: As of now, there is no way to compare values across types (in a standardized way).

# Known solutions to similar problems (in other environments):

- A simple Protocol: Simply add a Comparison protocol (with a compare/2 function) that a datatype can implement. This is similar to how many OOP-languages (including Ruby) 'implement' comparisons across types.

Main advantage: It only uses constructs that are already in the language right now (protocols).

Main drawback: Comparisons are supposed to work both ways, and be converse: `compare(1, Decimal(2))` should result in the exact opposite result of `compare(Decimal(2), 1)`. Using a simple protocol, this is not enforced at all: This might lead to duplicate code at best and unexpected behavior at worst.

- Ord: In other functional languages like Haskell (Clojure, Rust, ...), this is resolved by implementing the Ord typeclass (a typeclass is similar to an Elixir protocol) that works for comparisons of values of a single type. Comparisons across types are possible by (implicitly!) casting one value to the other beforehand.

Main advantage: This could probably be implemented using protocols/behaviours. (one for comparison of a certain type, one for casting type A to type B)

Main drawback: Implicit casting is happening behind the scenes, which sort of goes against the explicit nature of Elixir.

- Comparable 'Multimethod' It is possible to use a multimethod-like approach that dispatches based on the types of both of the things being compared instead of just the first argument.

Main advantage: The behaviour of this comparison is highly customizeable and would work between types.

Main drawback: This means the introduction of a new kind of construct (e.g. 'defcomparison') to the Elixir language.

[Wiebe-Marten Wijnja]

I have been thinking longer about this.

I think that the across-type implementation is overkill; I have a lot of trouble to come up with cases where this would be useful: Cases that I can think of can readily be solved by wrapping the inner structure in a containing struct, which is obviously more clear/explicit than providing a two-typed frankenprotocol.

I have been working on Numbers, which is basically dispatches arithmetic operations to any structs that implements its standardized Numeric behaviour. In this case, this means that functions/modules/structs can be written that wrap any kind of thing that implements the behaviour, which means that e.g. my Tensor library allows addition/multiplication to performed regardless of if the contents of the vectors/matrices/tensors are `Integer`s, `Float`s, `Decimal`s, `Ratio`nals or even `ComplexNum`bers.

I think that such a standardized way constructing something still is very important in the core language, because a standardized API means that modules consuming the API can use any modules(/data types) that are exposing the API.

I now envision the following, much simpler and less 'new language feature'-heavy than my original proposal:

---------------------

There is a normal protocol called Comparable, exposing two functions that can be overridden:

• compare(a, b) compares the two structs `a` and `b` of the same type. This function should return `:lt`, `:gt`, or `:eq` (keeping with the specification that DateTime.compare and Time.compare already follow). If there is no sensible way to compare the two types, a Comparable.CannotCompareError should be raised, with a describing error message. The Any implementation always raises this error.
• coerce(some_builtin_value).  Can optionally(!) be implemented to allow certain standard data types (e.g. numbers, or strings) to be automatically converted to the type of the thing we want to compare it with, to allow shorter notation for things like `compare(Decimal.new(2), 3)`. The Any implementation always raises Comparable.CannotCompareError.

There is a new function in the Kernel function Kernel.compare(a, b) has the following variants:

# struct <=> struct
Kernel.compare(a = %someStruct{}, b = %someStruct{}), do: Comparable.compare(a, b)
# struct <=> differentStruct
Kernel.compare(a = %someStruct{}, b = %someDifferentStruct{}), do: raise Comparable.CannotCompareError, message: "Cannot compare #{inspect(a)} with #{inspect(b)}."
# struct <=> builtin
Kernel.compare(a = %someStruct{}, b), do: Comparable.compare(a, Comparable.coerce(b))
# builtin <=> struct
Kernel.compare(a, b = %someStruct{}), do: Comparable.compare(Comparable.coerce(a), b)
# builtin <=> builtin, use Erlang's built-in term ordering.
Kernel.compare(a, b) when a == b, do: :eq
Kernel.compare(a, b) when a < b, do: :lt
Kernel.compare(a, b), do: :gt

[Allen Madsen]

`coerce` reminds me of Ruby's `coerce`, which serves the purpose of upgrading values, but can also swap the arguments. So, for example, if you had `1 + obj`, `obj` could have a method called `coerce` that took `1` and returned `[obj, 1]`. Then, ruby would treat that as `obj + 1` and use the `+` method from `obj` instead of `1`. The swapping of arguments are only useful as long as the operations are commutative, though.

Anyways, thought I'd mention the prior art in case it's useful.

Allen Madsen
http://www.allenmadsen.com

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscribe@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/a7e59ba9-699b-42db-a81f-cbda00179fc8%40googlegroups.com.

[Wiebe-Marten Wijnja]

I would like to revive this topic, because I am still looking for a good way to perform comparisons on custom structures.

Right now there is no standardized way to do this, resulting in widely varying APIs❧, many of which are incompatible with e.g. `Enum.sort` because of the chosen output format, which would be one of the most obvious and frequent use-cases of comparison operations.

So, I would like to propose the following:

• Add a `Comparable` protocol (Or behaviour?), containing `Comparable.compare(MyStruct.t, MyStruct.t)`.
• Choose a sensible output format for this compare function. This is something we should discuss: 
• In existing parts of Elixir Core (the (Date)(Time) modules), `:lt`, `:eq`, `:gt` are used. But these do not themselves follow the Erlang Term Ordering, and therefore cannot be used directly for things like`Enum.sort(enumerable, &Kernel.compare/2)`.
• Many other languages, and multiple existing libraries return an integer `-1, 0, 1`. This does follow the Erlang Term Ordering. Main disadvantage: They are not very descriptive, someone might think that any integer could be returned.
• `:<`, `:=`, `:>` are another possibility: Because of the ASCII ordering, these follow the Erlang Term Ordering, and are arguably more descriptive than the integers. Main disadvantage: They are not widely used yet. 
• What to do on error? Raise? Or return `nil`? `{:error, some_reason}` is another possibility (Although we do not use an `{:ok, success}` here, so maybe this is confusing?).
• Add `Kernel.compare/2`, which is overridden to use simple comparison for built-in datatypes, and dispatches to the protocol for structs (raising when the structs are not of the same type).

Aside from this, (this can be accepted/rejected independently!) I see value in a `Comparable.coerce(builtin)`, which can be optionally implemented to allow a builtin datatype to be converted to the struct of the other, before comparing.

❧ About widely-varying APIs:

- Time.compare, Date.compare, DateTime.compare return `:lt`, `:eq` or `:gt`

- Timex.compare returns integer (-1, 0, 1) or {:error, reason} and has an optional granularity.

- Decimal.compare returns #Decimal<-1>, #Decimal<0>, #Decimal<1> or #Decimal<NaN>. 

- Decimal.cmp returns `:lt`, :eq` or `:gt` and raises on NaN.

- Ratio.compare returns integer (-1, 0, 1) or raises Ratio.ComparisonError.

[Michał Muskała]

Just a quick remark (for anything more this requires a deeper analysis):

Why would erlang term ordering be important for the return value of compare/2 function? The function you pass to Enum.sort should return true or false, so you can't use it there directly anyway.

Michał.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.

To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/c55bd3c0-a2a9-4955-a62f-9184a587a029%40googlegroups.com.

[Wiebe-Marten Wijnja]

Thank you for your reply, Michał.

You are right, it does not. I don't know why I was thinking that Erlang Term Ordering would be important for Enum.sort.

This means that it probably is best to use `:lt`, `:gt`, `:eq` as outcome, since that is what Elixir itself already uses.

For proper use with Enum.sort, we could, besides `Kernel.compare/2` create `Kernel.lt?`,`Kernel.lte?`, `Kernel.equal?``Kernel.gte?`, `Kernel.gt?`, although this becomes such a large number of functions that we might put it under their own namespace (`Compare`?) instead.

We could change `Enum.sort` to use `&Kernel.lte?/2` by default, rather than `&<=/2`. Although this might have slight efficiency implications for existing applications, I think it would uphold the Principle of Least Surprise better.

[Michał Muskała]

On 9 Jun 2017, 14:28 +0200, Wiebe-Marten Wijnja <w.m.w...@panache-it.com>, wrote:

We could change `Enum.sort` to use `&Kernel.lte?/2` by default, rather than `&<=/2`. Although this might have slight efficiency implications for existing applications, I think it would uphold the Principle of Least Surprise better.

 

This would have huge performance implications. Enum.sort/1 and Enum.sort/2 have completely different implementations. Enum.sort/2 is about 2.5 times slower (when provided with &<=/2 as comparator).

Michał.

[Wiebe-Marten Wijnja]

After looking through the source of Elixir's `Enum` module and Erlang's `:lists` module, I now know that `:lists.sort` is implemented in plain Erlang, which means that it would also be possible to write multiple versions in Elixir (Most notably, both an low-to-high and high-to-low version). `Enum.sort(list) |> Enum.reverse()` is then slower than a hypothetical `Enum.sort_reverse(list)` by a constant factor. It might be interesting to benchmark this, but that is completely out of scope of the Comparable interface.

---

Going back to the core of this issue, I'd like for there to be a simple function `compare` with an accompanied Protocol, which ensures that the comparison return values are standardized. This would significantly improve compatibility of libraries. I think this is a standardization that we should embrace quickly, before the APIs of the publicly available libraries dift further apart and become near-impossible to reunite in a backwards-compatible fashion. 

I'd like to hear who is in favour and who is against of this very concrete proposal.

[OvermindDL1]

Sounds like precisely what is needed.  I'm all for it!

[Parker Selbert]

I'm strongly in favor of the proposal, it is an ideal use of protocols (and we aren't facing a non-BIF penalty).

— Parker

--

You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.

To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/a74bb762-546f-4856-8029-58fe48b30b30%40googlegroups.com.

[José Valim]

Hi  Wiebe-Marten Wijnja,

Thanks for the well-written proposal.

I am afraid my opinion has not changed much from the first time around.

The proposed solution would not support the "downcasting" done in `Date.compare`. `Decimal` may also want to perform casting as well.

And while I understand why it cannot support that and I would take the same decision as you, it makes it less appealing as we would still need a custom function in those cases.

And it may also be that those are actually better solved with a specific compare protocol, such as RataDieCompare or NumberCompare and not a general purpose one.

So I believe those protocols should be developed as a separate package and not included in Elixir.

I do understand the benefits of including it in Elixir itself but to me the conceptual cost of the new abstraction / mechanism outweighs the gains in this case.

I believe I have mentioned in the past the Decimal library is currently on the same situation.

It is very useful but, unless it is meant to integrate into the language in a more meaningful way, it will do just fine as a separate package.

[Wiebe-Marten Wijnja]

Hello Jose,

I completely understand where you are coming from. 

The main reason to add this to the core language is to standardize the return format of comparison functions. I believe this to be a very important idea.

Upcasting as in the case of Decimals can be supported using the coercion-mechanism explained earlier (and already implemented in the Numbers library: https://github.com/Qqwy/elixir_number/).

Downcasting as in the case of the (Naive)(Date)(Time) modules on the other hand is something that should happen explicitly in my opionion. Therefore, this feels like a feature that should not be supported on a protocol. Instead, I'd propose to keep the (Naive)(Date)(Tiime).compare functions for that purpose.

Again, the main important reason is to standardize the return type of the comparison functions.

If this is standardized, it becomes possible to write libraries that can build on top of it. Some ideas:

- An ExUnit add-on library that adds assertions like `assert_smaller`, `assert_not_equal` etc.

- Alternative container data structures that provide functionality based on the logical ordering of data structures (rather than the Erlang Term Ordering), such as priority queues that do not care if the priority is provided as a Decimal or a DateTime.

Right now, building those kinds of things is plain impossible, because you would need to handle the five different types of return values of `SomeModule.compare/2`. 

Another benefit I see is that programmers would not need to guess what kind of return value a comparison function has. 

Yesterday I spent half an hour debugging why a list of timestamps was not split at the correct location. Turns out I was doing `Timex.compare == :lt` whereas it should have been `Timex.compare == -1`, which is the kind of implicit implementation behaviour I'd like to not need to think about all the time as a programmer.

I do not feel that the comparison with Decimal makes a lot of sense, since this proposal is a lot smaller. Also, `compare/2` and `Comparable.compare/2` will integrate in the language quite a lot, since they will work for built-in types, expecting the two operands to be of the same type( both numbers, both lists, both binaries, both the same kind of struct, etc.).

Please standardize the way comparisons are made in the language. It is a very small addition but it will ensure that libraries are consistent in their APIs, allowing new libraries to flourish on top.

~Wiebe-Marten/Qqwy

[José Valim]

By integrating into the language, I mean in a way that it would yield large benefits only if made part of the language. The proposed solution and Decimal yield almost no benefits if part of Elixir compared to as a package, besides reachability.

Also, the current proposal for coerce doesn't handle coercing from struct to struct. If it does, it requires both sides implement the coercion and having an intermediate representation is almost always better.

If the goal is to standardize return types, then I think the best is to actually start using them in Elixir itself. We have already started with the calendar types, so others will be able to follow accordingly.

--

[Wiebe-Marten Wijnja]

> Also, the current proposal for coerce doesn't handle coercing from struct to struct. If it does, it requires both sides implement the coercion and having an intermediate representation is almost always better.

I am not really following your reasoning here. It seems like you state that not being able to handle struct<->struct coercions is a flaw of the proposal, but then you go on saying that having an intermediate representation is always better, meaning that coercion in these cases is not relevant.

> By integrating into the language, I mean in a way that it would yield large benefits only if made part of the language. The proposed solution and Decimal yield almost no benefits if part of Elixir compared to as a package, besides reachability.

The main reason why I believe that this should be integrated into the language is for the same reason that the (Naive)(Date)(Time)-structs were made part of the language: Consistency and therefore Interoptability between libraries.

A secondary but nearly as important reason would be that newcomers into the language quickly learn that using the standard comparison operators is not the way to go on custom data structures.

I am not sure what the process should be when implementing this outside of the core language: 

Should there be one library containing the protocol, and then for all libraries that happen to have comparison functionality another library that implements the protocol? (And thén also the libraries that build on top of the Comparable interface?)

Per the Dependency Inversion Principle, it would make more sense if Decimal, Timex, Ratio etc. would implement the Comparable protocol directly. However, the chance of this happening if 'Comparable' is just another Elixir library written by just another person is very low, because nothing is stopping any other person to write 'Comparable2' that works in a slightly different way and request from the authors to implement that one. A separate library lacks the authority required to standardize the comparison interface.

Ergo, this would mean that there would be a `comparable` library, and the 'compatibility-layer' libraries: `comparable_timex`, `comparable_decimal`, `comparable_ratio`, etc... And then finally libraries like `priority_queue` that are built on top of `comparable`. However, using these libraries that are built on top of 

`comparable` is not so nice, because the responsibility of making sure that the proper 'compatibility-layer' is loaded as a dependency shifts to the end user.

For example: if I then am building an application and need a priority queue, I'll need the `priority_queue` library, the `decimal` library and not forget to add the `comparable_decimal` library: 

Even though this is an implementation detail of PriorityQueue, it cannot have `comparable_decimal` as an dependency because that would not make sense for all the projects that do not use Decimal. 

There are many algorithms and data structures that would want to work with a Logical Ordering (rather than the Erlang Term Ordering). Including but not limited to:

- Sorting algorithms

- Searching algorithms

- Sets

- Multisets

- Maps

- Multimaps

- Trees (of which there are of course many shapes and kinds)

- Graphs and their related structures.

- Pathfinding algorithms.

- Permutation manipulation algorithms.

Working with partially and totally ordered data structures is something very universal. I know of at least:

- Haskell (the Ord typeclass), 

- Rust (the Ord trait), 

- Java (The Comparable interface), 

- .NET (the IComparable interface),

- Ruby (the spaceship <=> operator and `coerce`), 

- PHP (the spaceship <=> operator), 

- Python (functools.total_ordering() and __cmp__(a,b) and friends) 

- and C++ (the Comparable Concept).

All of them provide a built-in standardized way to implement custom logical comparisons for your data types, and because of this allow generic algorithms and data structures to be built on top.

I hope that I have proven with above arguments the importance of including standardized comparison functionality in the core language, rather than in a peripheral library which lacks the authority that is required for standardization.

~Wiebe-Marten/Qqwy

[José Valim]

I am not really following your reasoning here. It seems like you state that not being able to handle struct<->struct coercions is a flaw of the proposal, but then you go on saying that having an intermediate representation is always better, meaning that coercion in these cases is not relevant.

Exactly. The final point is the solution proposed is not going to be enough for many cases, with or without coercion.

The current proposal does not replace even the implementations of compare/2 within the language itself (which is within the calendar types). So if accepted, we will end-up with three mechanisms for comparing a date (one of them being the wrong one). And some data types may require yet another one, for example if we want to compare between Decimal and Ratio.

If the main goal of this proposal is standardization of return types, then I would rather achieve it through other mechanisms, such as adding uses of compare/2 in the language, which we have already done with (Naive)(Date)(Time).compare/2, and by adding :lt | :eq | :gt based comparison functions to Enum. Those would be necessary anyway if this proposal is accepted.

 

The main reason why I believe that this should be integrated into the language is for the same reason that the (Naive)(Date)(Time)-structs were made part of the language: Consistency and therefore Interoptability between libraries.

Those are fairly different scenarios:

* the (Naive)(Date)(Time) structs did not overlap with any existing concept in the language and effectively unified all uses of those structs in the community

* translation between calendar data types is much more complicated than the translation of compare results

* calendar types were always planned to be part of the language

Ergo, this would mean that there would be a `comparable` library, and the 'compatibility-layer' libraries: `comparable_timex`, `comparable_decimal`, `comparable_ratio`, etc... And then finally libraries like `priority_queue` that are built on top of `comparable`. However, using these libraries that are built on top of 

`comparable` is not so nice, because the responsibility of making sure that the proper 'compatibility-layer' is loaded as a dependency shifts to the end user.

Ideally, coordination between community members would happen to define protocols that are useful between libraries. However, I am still not convinced this protocol would be the correct choice for libraries such as Decimal and Ratio. In any case, that's why protocols are beautiful, because it allows any of the scenarios above. 

 

There are many algorithms and data structures that would want to work with a Logical Ordering (rather than the Erlang Term Ordering). Including but not limited to:

- Sorting algorithms

- Searching algorithms

- Sets

- Multisets

- Maps

- Multimaps

- Trees (of which there are of course many shapes and kinds)

- Graphs and their related structures.

- Pathfinding algorithms.

- Permutation manipulation algorithms.

Yes but those may also be OK with a Structural Ordering, which will certainly be faster, or may require a custom ordering. So the solution is not in adopting yet another limited implementation for ordering (because we already have one) but making sure a common return type is accepted, which as mentioned above, can be achieved through other ways.

[Wiebe-Marten Wijnja]

> The current proposal does not replace even the implementations of compare/2 within the language itself (which is within the calendar types). So if accepted, we will end-up with three mechanisms for comparing a date (one of them being the wrong one). And some data types may require yet another one, for example if we want to compare between Decimal and Ratio.

The only reason I do not propose to remove the `compare/2` that already exist within the (Naive)(Date)(Time) modules is to maintain backwards compatibility. I have not come across in practice any situation in which I found it convenient to directly compare one date/time version with another, throwing away precision in the process. This kind of downcasting is implicit and therefore I do not want to burden readers of my code with it.

The proposal does not try to solve all possible uses of comparisons, exactly because having something that both is a washing machine and a dishwasher makes for something that does not really excel at either of those tasks. Instead, the major use case of comparing two things of the same type, without upcasting or downcasting, is what this proposal tries to add.

> Yes but those [data types and algorithms] may also be OK with a Structural Ordering, which will certainly be faster, or may require a custom ordering. So the solution is not in adopting yet another limited implementation for ordering (because we already have one) but making sure a common return type is accepted, which as mentioned above, can be achieved through other ways.

When these structures use Structual Ordering, they will work differently from when using Logical Ordering.

An example: If I want to keep a top ten of highscores, I only want to order %HighScore{}'s based on their score, and not on the user that archieved the score or on the time the score was arrived at. A 'custom ordering' is exactly what this proposal wants to allow to be made.

Right now we are forced to either use Structual Ordering, or to re-create the desired algorithms and data types each time for every type that could have a Logical Ordering.

[José Valim]

When these structures use Structual Ordering, they will work differently from when using Logical Ordering.

An example: If I want to keep a top ten of highscores, I only want to order %HighScore{}'s based on their score, and not on the user that archieved the score or on the time the score was arrived at. A 'custom ordering' is exactly what this proposal wants to allow to be made.

If you want custom ordering, then a protocol is not the solution because they are global. Imagine you have a collection of users. Sometimes you want to order them by age, sometimes by name. Sure, you can implement the Comparable protocol for %User{} in a way that makes sense most times, but that doesn't exclude the fact you still want custom ordering via functions.

In fact, using a ordering that does not work across types would be detrimental in Elixir, since we do allow a list to have any data type. For example, if Enum.sort/1 used the proposed protocol, it would be unable to work on heterogeneous collection by default. If tree data types used that as well, we would be unable to have heterogenous trees, etc.

My point is: we already have an ordering mechanism. Sure, it has flaws, but there is little benefit in replacing it by a version that is slower and works only on homogenous collections. The answer is to continue supporting custom ordering functions. If we want to standardize the use of :eq | :lt | :gt, then let's do that by providing functions that work on those types. The answer is not a Comparable protocol.

[OvermindDL1]

On Saturday, June 17, 2017 at 12:01:33 PM UTC-6, José Valim wrote:

When these structures use Structual Ordering, they will work differently from when using Logical Ordering.

An example: If I want to keep a top ten of highscores, I only want to order %HighScore{}'s based on their score, and not on the user that archieved the score or on the time the score was arrived at. A 'custom ordering' is exactly what this proposal wants to allow to be made.

If you want custom ordering, then a protocol is not the solution because they are global. Imagine you have a collection of users. Sometimes you want to order them by age, sometimes by name. Sure, you can implement the Comparable protocol for %User{} in a way that makes sense most times, but that doesn't exclude the fact you still want custom ordering via functions.

This is precisely the case where Implicit Witness Modules are significantly better than the Data style uses that Haskell does (and that the proposed style here models).  You have an implicit default based on the type or can pass an explicit variant (OCaml is currently explicit for example, Scala is implicit and explicit, Elixir would have to be explicit like OCaml is since Elixir lacks types, though a typing library could fix that later), and the explicit version can be an entirely different implementation.

I'd really think the witness version would be far more powerful and more in line with how Elixir does it already, except you'd make it more generic and baked in (and `@behaviour`s would see a lot more use then too, no protocols needed and the dispatching is faster!).  It would have a similar cognitive load to how Elixir handles these already.

On Saturday, June 17, 2017 at 12:01:33 PM UTC-6, José Valim wrote: 

In fact, using a ordering that does not work across types would be detrimental in Elixir, since we do allow a list to have any data type. For example, if Enum.sort/1 used the proposed protocol, it would be unable to work on heterogeneous collection by default. If tree data types used that as well, we would be unable to have heterogenous trees, etc.

My point is: we already have an ordering mechanism. Sure, it has flaws, but there is little benefit in replacing it by a version that is slower and works only on homogenous collections. The answer is to continue supporting custom ordering functions. If we want to standardize the use of :eq | :lt | :gt, then let's do that by providing functions that work on those types. The answer is not a Comparable protocol.

Well how about a Witnesses style instead of a Data style?  I could make up a proposal with the awesome Qqwy based on them if you want to see that style considering it is similar to how Elixir does things already?

[Wiebe-Marten Wijnja]

I am not at all sure how a Witness-style proposal would look (The concept of witnesses is still a bit vague to me; I understand them as 'extra information passed to dispatch between implementations', but that would be very similar to the approach of just passing a comparison function directly). Please do go ahead and explain it in more detal! :-)

@Josevalim I have given the 'explicit comparison function' some thought. Indeed this seems like a more general and even less invasive 'solution' to the current problem. (Especially because we indeed always still want custom ordering via functions).

I think this will mean that frequently, data structures will contain the function that is used as comparison function internally. Which I think is fine, since functions even survive e.g. erl2bin -> bin2erl procedures.

Is it maybe helpful to create a `Comparable` behaviour containing `@callback comparable(a, b) :: :lt | :eq | :gt`, to set this design decision in stone (and thus give library developers a clear direction on which way to take)?

~Wiebe-Marten/Qqwy