[squeak-dev] Re: Collection>>sum implementation

[squeak-dev] Re: Collection>>sum implementation
Klaus D. Witzel klaus.witzel at cobss.com
Mon Aug 11 22:56:40 UTC 2008

Hi Klaus, Hi Randal

Thanks for your replys to my post.

On Mon, 11 Aug 2008 22:47:25 +0200, Randal L. Schwartz wrote:

>>>>>> "Jerome" == Jerome Peace <peace_the_dreamer at yahoo.com> writes:
>
> Jerome> You let it tell you:
>
> Jerome> any := myCollection anyOne  .
> Jerome> zeroElement := any - any .

***
Klaus>Problem here is that #() has no anyOne, and so #negated (assuming that
Klaus>sum wants to do #+) can also not be used.

Currently summing over the empty list signals an error.
That seems right.

If something needs the behavior otherwise it could wrap a call to sum with a check for special conditions
such as isEmpty or isNil. Then just return the special answer with a guard clause.

***
RandaL wrote:
> This presumes that anything that implements #+ is also expected
> to implement #-.  

Yes. #sum currently is spec'ed to assume that anyway.

In 3.10.2 only AbstractSound implements + without also implementing #-.

>Yes, that was also present in the original implementation,
> but a version that doesn't require that would be nice.

Why?
And why program it before it is needed?

And please look at the mantis report. It shows why the fix is needed.


Yours in service and curiosity, --Jerome Peace



     

On Tue, Aug 12, 2008 at 6:08 AM, Jerome Peace
<[hidden email]> wrote:
> [squeak-dev] Re: Collection>>sum implementation
> Klaus D. Witzel klaus.witzel at cobss.com
> Mon Aug 11 22:56:40 UTC 2008
>
> Currently summing over the empty list signals an error.
> That seems right.
>
> If something needs the behavior otherwise it could wrap a call to sum with a check for special conditions
> such as isEmpty or isNil. Then just return the special answer with a guard clause.

Agreed.

> RandaL wrote:
>> This presumes that anything that implements #+ is also expected
>> to implement #-.
>
> Yes. #sum currently is spec'ed to assume that anyway.

And that's wrong.  A sensible implementation of #sum should not need
subtraction!

>>Yes, that was also present in the original implementation,
>> but a version that doesn't require that would be nice.
>
> Why?
> And why program it before it is needed?
>
> And please look at the mantis report. It shows why the fix is needed.

*sigh*  Please read my message.  It is *obvious* that plain old
#inject:into: can't be used for #sum.  The solution is to have a new
method that fits the case better (e.g. #reduce: aBlock), not add an
element of the list in twice then take it out again.

Here is Lukas' implementation of SequencableCollection>>reduce:

reduce: aBlock
        | result |
        result := self first.
        2 to: self size do: [ :index |
                result := aBlock
                        value: result
                        value: (self at: index) ].
        ^ result

You see?  We take an element from the receiver as we must for the
reasons mentioned in the mantis report, *but we don't double process
it and we don't have to take it back out again*.  Simple and elegant
and also handles the case of an empty list with a sensible error
(#first fails with a bounds error).

>>>>> "Jason" == Jason Johnson <[hidden email]> writes:

Jason> Here is Lukas' implementation of SequencableCollection>>reduce:

Jason> reduce: aBlock
Jason> | result |
Jason> result := self first.
Jason> 2 to: self size do: [ :index |
Jason> result := aBlock
Jason> value: result
Jason> value: (self at: index) ].
Jason> ^ result

Jason> You see?  We take an element from the receiver as we must for the
Jason> reasons mentioned in the mantis report, *but we don't double process
Jason> it and we don't have to take it back out again*.  Simple and elegant
Jason> and also handles the case of an empty list with a sensible error
Jason> (#first fails with a bounds error).

Yes, that solves it for SequencableCollection, but not Collection.
I think the trouble is how to solve it for the general case.

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion

>>>>> "Randal" == Randal L Schwartz <[hidden email]> writes:

Randal> Yes, that solves it for SequencableCollection, but not Collection.
Randal> I think the trouble is how to solve it for the general case.

This may have been brought up before, but it just occurred to me
that we merely need an "InjectionNull" class that answers the first
argument in response to any message send, through a simple DNU handler.

Then we could implement #reduce: as:

reduce: aBlock
  self ifEmpty: [^ some exception ].
  ^self inject: InjectionNull new into: aBlock.

On the first round, the InjectionNull would answer the real
first element, and then we've bootstrapped our loop at full speed
for the remainder, regardless of whether it is sequenceable or not.

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion

Randal L. Schwartz wrote:
What about:

    | iteration |
    self ifEmpty: [ ^some exception ].
    iteration := [ :old :each | iteration := aBlock. each ].
    self do: [ :each | value := iteration value: value value: each ].
    ^value

Paolo

On Tue, Aug 12, 2008 at 4:43 PM, Randal L. Schwartz
<[hidden email]> wrote:
Interesting thought.

But the issue here is simply unordered collections, yes?  How do
unordered collections deal with #inject:into:?  Perhaps a possibility
would be to add a new method #inject:into:startingFrom: (or
#inject:into:skipping:) and implement the methods as:

inject: aVal into: aBlock
  ^ self inject: aVal into: aBlock startingFrom: 1

reduce: aBlock
  ^ self inject: self first into: aBlock startingFrom: 2

Of course unordered collections would have to specialize #reduce:
based on knowledge of their internal representation (i.e. how do we
pick an object and not traverse over it afterward).