Comparison for SequencableCollection

I was surprised when discovered that in Pharo comparison is not defined for lists, arrays and similar datastructures.

Because in almost every programming language (F#, Python, Javascript just to name few) you can compare lists, arrays, etc. By convention, the ordering is lexicographical, just like in strings.

It took little time to add needed methods to SequencableCollection, but I think its better to have them in core library (core image, or how do you call it?).

I'd say it is questonable if SequenceableCollections should be
comparable by default.

is (a b c) equal or lower than (b a c) ?
Doesn't this depend heavily on what is in the Collection and what the
meaning of the Sequence of two Collections is?

So I'd say there is not much use in putting comparisons into the base
class library, because there is a ton of assumptions about the
Collections in whatever implementation one can imagine. I would assume
that this is the job of some business object that holds objects in a
SequenceableCollection. Don't you think?

The fact that other languages provide such an implementation doesn't
mean much to me, to be honest. I choose a SequencableCollection in order
to keep objects in a certain order, nothing more, nothing less.

I think it is important to not get "overridden" by the fact that
something is extremely easy to do in Smalltalk. We can easily make bad
mistakes, just because we can.

Just my 2 cents

Joachim

Am 02.08.15 um 14:11 schrieb webwarrior:

--
-----------------------------------------------------------------------
Objektfabrik Joachim Tuchel          mailto:[hidden email]
Fliederweg 1                         http://www.objektfabrik.de
D-71640 Ludwigsburg                  http://joachimtuchel.wordpress.com
Telefon: +49 7141 56 10 86 0         Fax: +49 7141 56 10 86 1

Am 02.08.15 um 14:11 schrieb webwarrior:
> I was surprised when discovered that in Pharo comparison is not defined for
> lists, arrays and similar datastructures.
>
> Because in almost every programming language (F#, Python, Javascript just to
> name few) you can compare lists, arrays, etc. By convention, the ordering is
> lexicographical, just like in strings.

BTW: This would be SortedCollection, not OrderedCollection or its
superclass.
Still I am not convinced that I really need an implementation of #< in
SequencableCollection. Too many ways to interpret what greater or equal
or lower could mean...

On 02.08.2015 15:44, jtuchel [via Smalltalk] wrote:
> I'd say it is questonable if SequenceableCollections should be
> comparable by default.
>
> is (a b c) equal or lower than (b a c) ?
> Doesn't this depend heavily on what is in the Collection and what the
> meaning of the Sequence of two Collections is?

(a b c) = (b a c) if a = b
(a b c) < (b a c) if a < b

The semantics are well defined.

Of course, it depends on what's in collection! That's the point - we
compare collections by their content.
If some elements are not comparable, we'll get DoesNotUnderstand -
expected behavior when comparing non-comparable objects.

It's the same story as with equality.

> So I'd say there is not much use in putting comparisons into the base
> class library, because there is a ton of assumptions about the
> Collections in whatever implementation one can imagine. I would assume
> that this is the job of some business object that holds objects in a
> SequenceableCollection. Don't you think?

There is only one assumption - that elements of the first collection are
comparable to the elements of the second collection.

And I think that we shouldn't multiply entities beyond necessity by
creating a class when using simple datastructure would be sufficient.

> The fact that other languages provide such an implementation doesn't
> mean much to me, to be honest. I choose a SequencableCollection in order
> to keep objects in a certain order, nothing more, nothing less.

That's why we have methods such as polynomialEval: and
asDigitsToPower:do: (and I'm not talking about extension methods) ?

No. Sorted collection maintains order of its elements, and I'm talking
about order on [the set of] sequencable collections

On 02.08.2015 15:46, jtuchel [via Smalltalk] wrote:

> I'd say it is questonable if SequenceableCollections should be comparable by default.

+1

Alexandre
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On 02.08.2015 19:02, Peter Uhnák [via Smalltalk] wrote:
Technically, you can:
        (a < b) not and: [ (b < a) not ] "a and b are equal"

But of course it's reasonable to implement #= and #hash along with #< -
that's what TComparable requires.

> Compare it to sorting a collection, where you can either do #sorted,
> which will do "a <= b" by default, but you can still do #sorted: and
> specify the sort order, dtto with PluggableDictionary etc.
> So if anything, it would make more sense to be able to block-based
> testing (without relying on #<), because more often then not you will
> have your values wrapped in some (bigger) objects.

Something like #compare:using: where second argument is a binary block?
Might be a solution, although not as elegant.
Question is what are return values of the method and what is expected to
be returned from the block?
String>>#compare: returns integer from 1 to 3;
SequencableCollection>>#findBinary: expects either 0, negative or
positive integer; #sorted: expects boolean; #max:, #min:, etc. expect
object to be compared.

Your use case (comparing containers using pluggable comparison for
items) is pretty common.

And what I was suggesting won't solve that problem.

However, it will make sequencable collections with comparable items
comparable. That's it. If we have comparison defined for Point, why not
have it for arrays?

And no one forces you to define #= or #< for your objects if you don't
want to.


On 02.08.2015 20:23, Peter Uhnák [via Smalltalk] wrote:
>
> ... snip ...
>

Your use case (comparing containers using pluggable comparison for
items) is pretty common.

And what I was suggesting won't solve that problem.

However, it will make sequencable collections with comparable items
comparable. That's it. If we have comparison defined for Point, why not
have it for arrays?

And no one forces you to define #= or #< for your objects if you don't
want to.


On 02.08.2015 20:23, Peter Uhnák [via Smalltalk] wrote:
>
> ... snip ...
>

---

View this message in context: Re: Comparison for SequencableCollection
Sent from the Pharo Smalltalk Users mailing list archive at Nabble.com.

Am 02.08.15 um 15:23 schrieb webwarrior:
Are they? Why didn't the programmer use a Set then? She wanted to
preserve the order of objects, right? So the order if objects matters to
her, how does this weigh into your suggestion of comaprison? Don't get
me wrong: your suggestion sounds logical and is correct. But so are
others...

>
> Of course, it depends on what's in collection! That's the point - we
> compare collections by their content.
> If some elements are not comparable, we'll get DoesNotUnderstand -
> expected behavior when comparing non-comparable objects.
I am only talking about the sequence of objects. Ceteris paribus, what
does the fact that one of the objects has a higher index in one
collections mean in terms of being greater/equal/lower?

>
> It's the same story as with equality.
so at first sight, you are correct: (a b c) = (b a c) if a = b

But you aren't, because we are comparing Collections that only exist
because the order of objects matter. For whatever reason that we can
guess or not.
>
> > So I'd say there is not much use in putting comparisons into the base
> > class library, because there is a ton of assumptions about the
> > Collections in whatever implementation one can imagine. I would assume
> > that this is the job of some business object that holds objects in a
> > SequenceableCollection. Don't you think?
>
> There is only one assumption - that elements of the first collection are
> comparable to the elements of the second collection.

Only technically speaking.
But if you wanted to only make sure you have the same objects in two
collections, you'd probably use a Set or a Bag, no?

And then, looking deeper:
* What does it mean if element at position 3 in A is greater than B(3)
and A(4) is lower than B(4) and all others are equal?
* If collection A has 4 elements and B has 5. The first 4 are equal. Is
B greater or lower than A?


>
> And I think that we shouldn't multiply entities beyond necessity by
> creating a class when using simple datastructure would be sufficient.

I am trying to make a point about exactly this not being true. The
semantics of the sequence in a SequenceableCollection is completely out
of scope of the Collection class. SequenceableCollections make sure your
given ordering is preserved. But it has absolutely no idea why you chose
that order and what it is good for.

So while you are correct that we shouldn't build classes for no special
reason other than that we can, the example at hand is not an argument to
support it. It the sequence matters, then the semantics for the sequence
needs to be modelled. There needs to be a class that models the
knowledge about what the sequence is good for and - if necessary - can
decide whether it is greater or lower than another instance of that very
class. The SequenceableCollection is a data structure, not a business
object. If there is semantics to a sequence, it is business knowledge.




>
> > The fact that other languages provide such an implementation doesn't
> > mean much to me, to be honest. I choose a SequencableCollection in
> order
> > to keep objects in a certain order, nothing more, nothing less.
>
> That's why we have methods such as polynomialEval: and
> asDigitsToPower:do: (and I'm not talking about extension methods) ?
Maybe these methods have gotten where they are for the same reasons
people use Associations and Dictionary all over the place. Laziness.
Most of the times, this smells like technical debt.

Joachim

--
-----------------------------------------------------------------------
Objektfabrik Joachim Tuchel          mailto:[hidden email]
Fliederweg 1                         http://www.objektfabrik.de
D-71640 Ludwigsburg                  http://joachimtuchel.wordpress.com
Telefon: +49 7141 56 10 86 0         Fax: +49 7141 56 10 86 1

We're drifting too much into philosophy here. Meaning of this, meaning
of that...

I'd argue there is no intrinsic meaning in statements such as "string A
is less than string B". But it is useful to have order defined on set of
words and character strings in general. Lexicographic order has some
useful properties and has been used in dictionaries for a long time.

Now nobody (OK, maybe I'm exaggerating a bit) questions whether strings
should have comparison and what ordering to use. We can easily
generalize this to all sequences with elements that can be compared -
and that's what designers of programming languages did. So it became
like de facto standard.

Note that default lexicographic ordering for strings is not always
desired - e.g. some file browsers have option of "numerical order"
(which accounts for numbers - "10" comes after "9" and so on). Still
it's not a reason to abandon default ordering.

On a side note: some functional programming languages with ADTs
(algebraic data types) automatically provide structural equality and
comparison for all ADTs, including user-defined, where it is possible.
And it's awesome, because it saves you from writing boilerplate code.
Again, you could say that there is no meaning in comparison of, say,
some n-ary trees of bools. But it has practical use: a datatype must
implement comparison to be used in sets and dictionaries that are based
on search trees.


On 03.08.2015 16:37, jtuchel [via Smalltalk] wrote:
>
> ...snip...
>

On Mon, Aug 3, 2015 at 12:04 AM, Peter Uhnák <[hidden email]> wrote:
>> (a b c) = (b a c) if a = b
>>
>> (a b c) < (b a c) if a < b
>> The semantics are well defined.

A comparison between sequenceable collections compares each element in sequence.
This makes intutive sense.

> Since you mentioned JavaScript, you should know that you can't compare
> arrays with ==, because it does object comparison.

I don't understand the introduction of == to the argument. Its not
mentioned previously.

>> No. Sorted collection maintains order of its elements, and I'm talking
>> about order on [the set of] sequencable collections
>
> This will make sense only if the objects have overriden their #=.

It seems okay to me for the user to be responsible for ensuring
elements put into SequenceableCollection can be compared.

Learning things from other languages *is* a reasonable argument, but
it should not be the major consideration.
cheers -ben

Am 04.08.15 um 00:22 schrieb webwarrior:
> We're drifting too much into philosophy here. Meaning of this, meaning
> of that...
Thanks. I'd love to be clever enough to be a philosopher.
>
> I'd argue there is no intrinsic meaning in statements such as "string A
> is less than string B". But it is useful to have order defined on set of
> words and character strings in general. Lexicographic order has some
> useful properties and has been used in dictionaries for a long time.
The only thing I am worried about here is that you use the word
"intrinsic".
Other than that, you are fully correct. In daily life, we've grown
accustomed to a being the letter before b. Not intrinsically, but
practically.

Not sure what exactly this has to do with Collections that hold any kind
of objects.

Please implement comparison and move it to the Pharo base library,
because, since there is no intrinsic meaning to comparing collections
anyway, you can do whatever you want, as long as it is well-defined and
it can be overridden if needed. Just because I am saying this is pollution
and questionable, you shouldn't keep yourself from doing so. Oh, now it's you who drifts into philosophy. You just said it's well
defined and therefor okay to have some default ordering. Now daily life
jumps in and jumps onto your fine arguments and breaks everything.

And then, the whole Unicode catastrophe around differences between
languages and cultures just shows that oversimplifying can be expensive
errors. You say nobody questions if A<B, admitting it may be
exaggerating. In reality there are several billions of people on the
planet who wouldn't really care because neither A nor B are used in
their mother language. This, of course, is philosophocal and I apologize
immediately.
My point is that lexical ordering is business logic, and we currently
see what a mess we made when we decided to use the roman alphapet
exclusively for lexical ordering. We just locked out 40-50% of the human
race from having any meaning in ordering. Maybe lexical ordering should
be pluggable, just because it is not intrinsic. Because the order of
things is often dependent on context. And context is something that is
not well suited for a base class library if it is not designed as
something extendible/configurable.

I admit I am at the edge of philosophy here, because what the heck does
this "oh, the chinese use pictures instead of letters" have to do with
an abstract definition of comparison between collections?

>
> On a side note: some functional programming languages with ADTs
> (algebraic data types) automatically provide structural equality and
> comparison for all ADTs, including user-defined, where it is possible.
> And it's awesome, because it saves you from writing boilerplate code.
> Again, you could say that there is no meaning in comparison of, say,
> some n-ary trees of bools. But it has practical use: a datatype must
> implement comparison to be used in sets and dictionaries that are based
> on search trees.
Fair enough. Most of the times, you implement your real-life meaning of
comparison and equality to make good use of such features. Or you don't
care if there is no order, just the need for fast retrieval based on
criteria you don't care about. I am not familiar with the definition of
ADT, but "algebraic" seems to indicate there is some mathematical set of
base rules that needs to be met by those data types, right? You make
them algebraic by making sure they follow the rules of algebra. Once
that's ensured, everything else is just that: algebra.

Again: A Sequenceable Collection makes sure objects are kept in a
defined order. "Definition" here is either some kind of sorting (you use
or override equality and comparison) or the order of adding to the
collection, or something else. That is the job of a
SequenceableCollection. Nothing more, nothing less.

But please let's end this discussion, I will try not to write anything
more on the topic. I stated my opinion which you asked for. If you don't
agree, good. I don't consider myself intelligent enough to redefine
Smalltalk, but in this case I have the feeling your idea doesn't qualify
for the base libraries. You know that by now, we disagree. good.

Joachim

--
-----------------------------------------------------------------------
Objektfabrik Joachim Tuchel          mailto:[hidden email]
Fliederweg 1                         http://www.objektfabrik.de
D-71640 Ludwigsburg                  http://joachimtuchel.wordpress.com
Telefon: +49 7141 56 10 86 0         Fax: +49 7141 56 10 86 1