SortedCollection>>reverse answers an inconsistent object in Pharo 6

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method.  It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r

Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
I know perfectly well what the problem is.
I explained it in my message: the inherited #reversed
method doesn't know the sortBlock exists.
(So whether it is nil or not is not relevant.)

I also know several ways to fix it, and provided
tested source code for one of them in my message.
Using (a <= b) not would be a bad idea as a
sortBlock is supposed to act like #<=, not like #<.

(That has always puzzled me: why take #< as the
fundamental operation in Magnitude but #<= as the
fundamental operation in sorting?  But that is
historic and standard practice.)

On 23 April 2018 at 19:10, Erik Stel <[hidden email]> wrote:
Richard,

The 'problem' is that the result of the (original) #reverse is a
SortedCollection without a sortBlock. Meaning it defaults to comparing
values using #<=. When a new element is added to the reversed collection it
simply assumes all elements are already sorted and uses the (default)
sortBlock to add a new element.

I think the solution should be to have #reverse add an explicit sortBlock
which consists of reversing the original sortBlock or defaulting to [ a: b:
| (a <= b) not ]. (Keep #<= as some classes might depend on only
implementing this)

Cheers,
Erik




--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html


Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Erik Stel
I already deleted my post (within 1 minute after posting 8-) seeing that I
jumped the wagon too early. Sorry for that. Your message and proposed
solution is fine.



--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Erik Stel
In reply to this post by Richard O'Keefe
Richard,

Can you explain me what you mean by "sortBlock is supposed to act like #<="?
Isn't it up to the developer to decide what the logic should be? I simply
used #<= because #> might not have been implemented for all relevant
classes, but would otherwise have chosen #> as a means to get the 'reversal'
of #<=.

Your solution is not resulting in the behaviour I would expect it. Adding
elements which are compared equally, but still have a different value, do
not get added in the same position. In the examples below I use
Associations, since it compares on the key only (for #<= comparison).

Consider a regular SortedCollection with default sortBlock (set explicitly):
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | a <= b ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

When I create a SortedCollection with your code's sortBlock reversed I get:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | b <= a ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

The order of the result is the same in both situations. What I would expect
is the result you get from the sortBlock I suggested:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | (a <= b) not ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Other' #k->'Or' #k->'Value' #k->'Some')"

This last result is the reversal of the original result.

(side note)
IF in the above #addAll: was used instead of the repeated #add:, things
might be different again. Since the #addAll: implementation would on some
occasions (when size of receiver vs size of added elements is certain ratio)
add the elements at the end and then perform a #reSort. With values being
compared as equal, the order will be decided by the order they were added.
So the result of #addAll: depends on the collection sizes. This might not be
what a user would expect ;-).



--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
"sortBlock is supposed to act like #<=" means
"for every triple of elements x y z that might be
 in the collection,
  b(x,x) is true
  b(x,y) is Boolean
  b(x,y) | b(y,x)
  b(x,y) & b(y,z) implies b(x,z)."
The first condition distinguishes it from #< .
In particular, if you want to sort a sequence
of *identical* elements, the sortBlock must
satisfy b(x,x).

There are other predicates around that act like
<= in the relevant sense: >= for example.
But #beginsWith: and #endsWith: don't satisfy
dichotomy.


On 24 April 2018 at 02:43, Erik Stel <[hidden email]> wrote:
Richard,

Can you explain me what you mean by "sortBlock is supposed to act like #<="?
Isn't it up to the developer to decide what the logic should be? I simply
used #<= because #> might not have been implemented for all relevant
classes, but would otherwise have chosen #> as a means to get the 'reversal'
of #<=.

Your solution is not resulting in the behaviour I would expect it. Adding
elements which are compared equally, but still have a different value, do
not get added in the same position. In the examples below I use
Associations, since it compares on the key only (for #<= comparison).

Consider a regular SortedCollection with default sortBlock (set explicitly):
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | a <= b ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

When I create a SortedCollection with your code's sortBlock reversed I get:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | b <= a ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

The order of the result is the same in both situations. What I would expect
is the result you get from the sortBlock I suggested:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | (a <= b) not ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Other' #k->'Or' #k->'Value' #k->'Some')"

This last result is the reversal of the original result.

(side note)
IF in the above #addAll: was used instead of the repeated #add:, things
might be different again. Since the #addAll: implementation would on some
occasions (when size of receiver vs size of added elements is certain ratio)
add the elements at the end and then perform a #reSort. With values being
compared as equal, the order will be decided by the order they were added.
So the result of #addAll: depends on the collection sizes. This might not be
what a user would expect ;-).

Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
In reply to this post by Erik Stel
Let me offer a simple example.
#(a a) isSortedBy: [:x :y | (x <= y) not]
is false, while
#(a a) isSortedBy: [:x :y | y <= x]
is true.

On 24 April 2018 at 02:43, Erik Stel <[hidden email]> wrote:
Richard,

Can you explain me what you mean by "sortBlock is supposed to act like #<="?
Isn't it up to the developer to decide what the logic should be? I simply
used #<= because #> might not have been implemented for all relevant
classes, but would otherwise have chosen #> as a means to get the 'reversal'
of #<=.

Your solution is not resulting in the behaviour I would expect it. Adding
elements which are compared equally, but still have a different value, do
not get added in the same position. In the examples below I use
Associations, since it compares on the key only (for #<= comparison).

Consider a regular SortedCollection with default sortBlock (set explicitly):
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | a <= b ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

When I create a SortedCollection with your code's sortBlock reversed I get:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | b <= a ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Some' #k->'Value' #k->'Or' #k->'Other')"

The order of the result is the same in both situations. What I would expect
is the result you get from the sortBlock I suggested:
| aCollection |
aCollection := SortedCollection sortBlock: [ :a :b | (a <= b) not ].
{#k->'Some'. #k->'Value'. #k->'Or'. #k->'Other'} do: [ :each | aCollection
add: each ].
aCollection.
 "a SortedCollection(#k->'Other' #k->'Or' #k->'Value' #k->'Some')"

This last result is the reversal of the original result.

(side note)
IF in the above #addAll: was used instead of the repeated #add:, things
might be different again. Since the #addAll: implementation would on some
occasions (when size of receiver vs size of added elements is certain ratio)
add the elements at the end and then perform a #reSort. With values being
compared as equal, the order will be decided by the order they were added.
So the result of #addAll: depends on the collection sizes. This might not be
what a user would expect ;-).

Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Erik Stel
Why does the sortBlock has to answer true for the same (identical) object? I
have not been able to find where it is specified. And in different locations
I see #> being used as a comparator for the sortBlock. So why is it bad (as
you wrote)? (It seems you describe that SortedCollection should create a
collection with a Total Order, whereas I describe a situation where a Strict
Order is also valid.)




--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Denis Kudriashov
In reply to this post by Richard O'Keefe
Hi Richard.

I agree with your proposal. 
But it force me to think that we should completely move to SortFunction's. 
In that case SortCollection will have sortFunction variable instead of sortBlock. And for your scenario reverse operation will be simple expression: "sortFunction := sortFunction reversed".



2018-04-23 3:09 GMT+02:00 Richard O'Keefe <[hidden email]>:
Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method.  It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r


Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
In reply to this post by Erik Stel
As I pointed out yesterday, #sort and its immediate relatives
are not alone.  Look at #isSortedBy: .  When do you want
(#(1 1 1) asSortedCollection: b) isSortedBy: b
to answer false?

There are several reasons for sorting.  One is so that you
can use binary search.  It's rather disconcerting that the
binary search offered in Squeak and Pharo has nothing to do
with sortBlocks.  In several other Smalltalks it does.  It
is not terribly hard to write a binary search using a
sortBlock that acts like #<=.  It is not terribly hard to
write a binary search using a sort block that acts like
#<.  It is harder than it needs to be to write a binary
search that can tolerate either, and the one Smalltalk I
know that does this copes by calling the sortBlock twice
as often as it would need to if it knew one way or the other.

As it happens, my own Smalltalk library lets me do
sortBlock := sortBlock converse, which makes it easy
to do the right thing.  It is possible to implement this
so that the result is as cheap to call as the original.


Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
In reply to this post by Denis Kudriashov
(aSortFunction value: x value: y) returns a Boolean;
(aSortFunction value: x value: x) returns true.
So you can already set up a SortedCollection using
a SortFunction.  So yes, that would work.
But there is no reason why #reversed (or my preference,
#converse) could not work on sortBlocks.


On 25 April 2018 at 23:27, Denis Kudriashov <[hidden email]> wrote:
Hi Richard.

I agree with your proposal. 
But it force me to think that we should completely move to SortFunction's. 
In that case SortCollection will have sortFunction variable instead of sortBlock. And for your scenario reverse operation will be simple expression: "sortFunction := sortFunction reversed".



2018-04-23 3:09 GMT+02:00 Richard O'Keefe <[hidden email]>:
Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method.  It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r



Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Denis Kudriashov
2018-04-25 14:26 GMT+02:00 Richard O'Keefe <[hidden email]>:
(aSortFunction value: x value: y) returns a Boolean;
(aSortFunction value: x value: x) returns true.
So you can already set up a SortedCollection using
a SortFunction.  So yes, that would work.

Yes. It was original goal to introduce them. 
I created another thread in dev list "SortedCollection based on SortFunction".
 
But there is no reason why #reversed (or my preference,
#converse) could not work on sortBlocks.

It will. But I think it is bad approach. Because any time you will need new kind of sort operation you will be forced extend BlockClosure.
In general reversed/converse has no meaning for block.

With SortFunction only simple extension #asSortFunction is required.
  


On 25 April 2018 at 23:27, Denis Kudriashov <[hidden email]> wrote:
Hi Richard.

I agree with your proposal. 
But it force me to think that we should completely move to SortFunction's. 
In that case SortCollection will have sortFunction variable instead of sortBlock. And for your scenario reverse operation will be simple expression: "sortFunction := sortFunction reversed".



2018-04-23 3:09 GMT+02:00 Richard O'Keefe <[hidden email]>:
Test case:
   #(1 2 4) asSortedCollection reverse add: 3; yourself
<print it>
The answer *should* be aSortedCollection(4 3 2 1)
but *is* aSortedCollection(4 2 1 3).
This works in Squeak.
The problem is that SortedCollection does not define
#reverse[d] but simply inherits it(them), and the
inherited code pays no attention to the sortBlock.

I propose adding the following two methods to
SortedCollection:

reverseInPlace
    |a z|
    a := firstIndex.
    z := lastIndex.
    [a < z] whileTrue: [array swap: a with: z. a := a + 1. z := z - 1].
    sortBlock := sortBlock
        ifNil: [[:x :y | y <= x]]
        ifNotNil: [[:x :y | sortBlock value: y value: x]].
    ^self

reversed
    ^self copy reverseInPlace

The ANSI method is #reverse, not #reversed, but Pharo
defines #reverse to call #reversed, and OrderedCollection overrides #reversed, so SortedCollection *must* override #reversed.

#reverseInPlace is the name Squeak uses for the other
method.  It also has a definition in SequenceableCollection, which is not but is
equivalent to

reverseInPlace
    |a z|
    a := 1.
    z := self size.
    [a < z] whileTrue: [self swap: a with: z. a := a + 1. z := z - 1].l
    ^self

r




Reply | Threaded
Open this post in threaded view
|

Re: SortedCollection>>reverse answers an inconsistent object in Pharo 6

Richard O'Keefe
You wrote "In general reversed/converse has no meaning for block."
That's entirely an artefact of representing blocks of different
arities by the same class.  In my own Smalltalk, NiladicBlock,
MonadicBlock, DyadicBlock, ... are different classes.  To put it
another way, your statement has exactly the same status as
"In general #value:value: has no meaning for block."
#converse has meaning for *all* DyadicBlocks, it is the
combinator flip f x y = f y x.  For that matter, it could
be generalised to all blocks of arity >= 2 as
[:a1 :a2 ... :an | body] converse
=> [:a2 :a1 ... :an | body]
i.e., flip the first two arguments.

My original implementation of #converse was
DyadicBlock
  methods for: 'combinators'
    converse
      ^[:x :y | self value: y value: x]
    "other combinators"

With a suitable set of combinators, I can do things like
#name ascending thenBy: #age descending thenBy: #weight ascending nilsFirst
without needing a SortFunction class.

​I do like the fact that SortFunction can support both 2-way and 3-way​
comparison.