[Pharo-users] Re: Picking neighbouring elements
I'm sorry, it appears that I failed to explain the question
well enough. I thought I'd explained earlier.
successor: target
^(self select: [:each | target < each]) min
is trivial. What's wrong with it is that it allocates
an intermediate collection and takes two passes.
FIXING that is is also trivial.
successor: target
^(self virtualSelect: [:each | target < each]) min
^^^
This does allocate something, but it's just a few words,
and a single traversal is one.
In other languages/contexts we'd be talking about
loop fusion/listless transformation/deforestation.
It is my understanding that using Transducers would
get me *this* level of improvement.
The problem is that this is still a linear-time
algorithm. If you take advantage of the order in
a SortedCollection or SortedSet,it can take logarithmic
time. When SortedSet is implemented as a splay tree
-- as it is in my library -- iterating over all its
elements using #successor: is amortised CONSTANT time
per element. So we need THREE algorithms:
- worst case O(n) select+min
- worst case O(lg n) binary search
- amortised O(1) splaying
and we want the algorithm selection to be
A U T O M A T I C.
That's the point of using an object-oriented language.
I say what I want done and the receiver decides how to
do it. Anything where I have to write different
calling code depending on the structure of the receiver
doesn't count as a solution.
Now we come to the heart of the problem.
The binary search algorithm is NOT a special case
of the linear search algorithm. It is not made of
pieces that can be related to the parts of the linear
search algorithm.
The splaying algorithm is NOT a special case of the
linear search algorithm OR the binary search algorithm.
It is not made of pieces that can be related to their
parts.
So *IF* I want automatic selection of an appropriate
algorithm, then I have to rely on inheritance and
overriding, and in order to do that I have to have
a named method that *can* be overridden, and at that
point I'm no longer building a transducer out of
pluggable pieces.
So that's the point of this exercise.
How do we get
(a) composition of transducers out of pluggable parts
AND
(b) automatic selection of appropriate algorithms
On Fri, 21 Apr 2023 at 20:35, Steffen Märcker wrote:
> Hi Richard,
>
> Now that's much clearer to me:
> min{y | y in c . y > x} "strict supremum"
> max{y | y in c . y < x} "strict infimum"
>
> For the general case of a sequence (not sorted) of elements we can do
>
> strictSupremumOf: x in: sequence
>
> ^(sequence transduce filter: [:y | y > x]) "virtual sequence"
> inject: nil
> into: [:min :b | min ifNotNil: [:a | a min: b]]
>
> I just picked a variant of minimum that answers nil if no element is
> found. Other variants would work, too.
> The focus of transducers is on re-use and composition of processing steps.
> We can break this up into steps if needed:
>
> minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil.
> "reduction"
> upperBounds := Filter predicate: [:y | y > x]. "transducer"
> strictSup := minimum transduce: upperBounds. "transformed reduction"
> ^strictSup reduce: sequence
>
> We can also use a different notation similar to a data flow:
>
> minimum <~ upperBounds <~ sequence
>
> Of course, if we know how the sequence is sorted, we should use another
> algorithm. Assuming an ascending order with no random access, we'd change
> minimum to stop early:
>
> minimum := [:min :b | Stop result: b].
>
> Kind regards,
> Steffen
>
>
> Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00):
>
> successor of x in c = the smallest element of c that is larger than x
> min {y | y in c . y > x}
> predecessor of x in c = the largest element of c that is smaller than x
> max {y | y in c . y < x}
>
> On Thu, 20 Apr 2023 at 21:08, Steffen Märcker wrote:
>
>> Dear Richard,
>>
>> thanks for that additional piece. I'll put insert- on my list
>> of possible variants. I think we come back to naming after the initial port
>> is done and everyone can play with it. Generally, I made the observation to
>> better be careful with names since it's too easy to alienate other or
>> trigger wrong assumptions.
>>
>> New topic! (quote below)
>>
>> Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I
>> am having difficulties understanding what exactly these operations with a
>> sequence of elements. Can you give an example or some pseude/smalltalk code
>> from your use-case and library?
>>
>> Kind regards
>>
>>
>> Changing the subject a wee bit, there's an operation family
>> in my library, and I wonder how it would fit into Transducers?
>> To avoid bias, here's a specification in Haskell (for lists,
>> because I haven't had any luck installing Data.Witherable).
>>
>> uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a
>> successor, predecessor :: Ord a=> a -> [a] -> a
>>
>> successor = successorBy compare
>>
>> successorBy
[Pharo-users] Re: Picking neighbouring elements
Hi Richard,
Now that's much clearer to me:
min{y | y in c . y > x} "strict supremum"
max{y | y in c . y < x} "strict infimum"
For the general case of a sequence (not sorted) of elements we can do
strictSupremumOf: x in: sequence
^(sequence transduce filter: [:y | y > x])
"virtual sequence"
inject: nil
into: [:min :b | min ifNotNil: [:a | a min: b]]
I just picked a variant of minimum that answers nil if no element is found.
Other variants would work, too.
The focus of transducers is on re-use and composition of processing steps. We
can break this up into steps if needed:
minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil.
"reduction"
upperBounds := Filter predicate: [:y | y > x].
"transducer"
strictSup := minimum transduce: upperBounds.
"transformed reduction"
^strictSup reduce: sequence
We can also use a different notation similar to a data flow:
minimum <~ upperBounds <~ sequence
Of course, if we know how the sequence is sorted, we should use another
algorithm. Assuming an ascending order with no random access, we'd change
minimum to stop early:
minimum := [:min :b | Stop result: b].
Kind regards,
Steffen
Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00):
successor of x in c = the smallest element of c that is larger than x
min {y | y in c . y > x}
predecessor of x in c = the largest element of c that is smaller than x
max {y | y in c . y < x}
On Thu, 20 Apr 2023 at 21:08, Steffen Märcker wrote:
Dear Richard,
thanks for that additional piece. I'll put insert- on my list of
possible variants. I think we come back to naming after the initial port is
done and everyone can play with it. Generally, I made the observation to better
be careful with names since it's too easy to alienate other or trigger wrong
assumptions.
New topic! (quote below)
Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I am
having difficulties understanding what exactly these operations with a sequence
of elements. Can you give an example or some pseude/smalltalk code from your
use-case and library?
Kind regards
Changing the subject a wee bit, there's an operation family
in my library, and I wonder how it would fit into Transducers?
To avoid bias, here's a specification in Haskell (for lists,
because I haven't had any luck installing Data.Witherable).
uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a
successor, predecessor :: Ord a=> a -> [a] -> a
successor = successorBy compare
successorBy cmp x = minimumBy cmp . filter (\y -> cmp x y == LT)
predecessor = predecessorBy compare
predecessorBy cmp = successorBy (flip cmp)
The reason these operations exist is to pick neighbouring
elements in SortedCollections and SortedSets. But they make
*sense* for any Enumerable. So there are "generic"
definitions with orderrides for those two classes.
A filter + a reduce . Traditionally, a #select:thenFold:ifNone:
in order to avoid building an intermediate collection. That much
I see how to do with transducers. But you can't get the desired
override for #successor:[sortBlock:][ifNone:] by overriding
#select:thenFold:ifNone: in SortedCollection or SortedSet. So what
*should* one do?
--
Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter vivaldi.com
herunter
[Pharo-users] This week (16/2023) on the Pharo Issue Tracker
We merged ~60 PRs this week. # Pharo 11 - Backport #13426: Make protocol of super method a priority in MethodClassifier #13432 https://github.com/pharo-project/pharo/pull/13432 - Use fixed spec version for Pharo 11 #13445 https://github.com/pharo-project/pharo/pull/13445 ## GIT/Iceberg (for Pharo 12, too) - 1279 merge menu should indicate the sense of the action #1680 https://github.com/pharo-vcs/iceberg/pull/1680 - Remove unused variable #1695 https://github.com/pharo-vcs/iceberg/pull/1695 - Fix for adding a SSH credential from UI raises an Error #1638 https://github.com/pharo-vcs/iceberg/pull/1638 - Use ED25519 keys as default instead of RSA to improve security and follow new GitHub standards #1649 https://github.com/pharo-vcs/iceberg/pull/1649 - [fix] prevent Iceberg window to crash when the registry is empty #1670 https://github.com/pharo-vcs/iceberg/pull/1670 - Fix for issue #11969 in pharo repository: Better description "packages unloaded packages #1672 https://github.com/pharo-vcs/iceberg/pull/1672 #Pharo 12 ## Enhancements - Completion menu: some love on the detail window #13473 https://github.com/pharo-project/pharo/pull/13473 - Use Pharo12 branch of Spec and NewTools #13460 https://github.com/pharo-project/pharo/pull/13460 - Fix random failure of Ombu in windows. #13448 https://github.com/pharo-project/pharo/pull/13448 - Make protocol of super method a priority in MethodClassifier #13426 https://github.com/pharo-project/pharo/pull/13426 - Cut dependency from CommandLine to UIManager #13431 https://github.com/pharo-project/pharo/pull/13431 - Fix typo introduced in merge #13446 https://github.com/pharo-project/pharo/pull/13446 - Added inspector extensions for RPackage #509 https://github.com/pharo-spec/NewTools/pull/509 ## RPackage and SystemOrganizer - Synch bug in RPackage removal #13496 https://github.com/pharo-project/pharo/pull/13496 ## Protocol and Categories - Keep pushing protocols usage #13443 https://github.com/pharo-project/pharo/pull/13443 - Add some tests on classifications of methods #13485 https://github.com/pharo-project/pharo/pull/13485 - Rename #removeMethodTag: into #removeProtocolIfEmpty: #13492 https://github.com/pharo-project/pharo/pull/13492 - Make #renameProtocolNamed:toBe: manage nils #13480 https://github.com/pharo-project/pharo/pull/13480 - Cleaning of #classify:inProtocolNamed: #13454 https://github.com/pharo-project/pharo/pull/13454 - Deprecate comment management of ClassOrganization #13464 https://github.com/pharo-project/pharo/pull/13464 - Remove ClassOrganization>>#silentlyRenameProtocolNamed:toBe: in favor of always announcing the rename #13458 https://github.com/pharo-project/pharo/pull/13458 - Improve ClassOrganization copy #13453 https://github.com/pharo-project/pharo/pull/13453 - Do not use #classComment #1376 https://github.com/pharo-spec/Spec/pull/1376 ## Compiler: Syntax Hightlight - SHRBTextStyler class>>#blueStyleTable distinguish some variables #13501 https://github.com/pharo-project/pharo/pull/13501 - Improve style for parenthesis, comments and syntax error #13491 https://github.com/pharo-project/pharo/pull/13491 - CodeSnippet: industrialize the testing of the styler #13490 https://github.com/pharo-project/pharo/pull/13490 - add SHRBStyleAttributionTest>>#testErrorStyle #13489 https://github.com/pharo-project/pharo/pull/13489 - Faulty code: improve highlight and icons #13486 https://github.com/pharo-project/pharo/pull/13486 - Fix bug in parenthesis highlight #13467 https://github.com/pharo-project/pharo/pull/13467 ## Compiler: AST - AST: starting visiting comments #13421 https://github.com/pharo-project/pharo/pull/13421 - Snippet: test more comments and fix some #13500 https://github.com/pharo-project/pharo/pull/13500 - Add support to deprecate globals #13348 https://github.com/pharo-project/pharo/pull/13348 - Compiler: expose the AST #13487 https://github.com/pharo-project/pharo/pull/13487 ## Compiler - Snippets: rename (and negate) isMethod to isScripting #13499 https://github.com/pharo-project/pharo/pull/13499 - Vocabulary: propose "script" in compiler #13301 https://github.com/pharo-project/pharo/pull/13301 - OpalCompiler: permit clients to use receiver: after context: as (a noop) #13498 https://github.com/pharo-project/pharo/pull/13498 - Introduce annotations #13449 https://github.com/pharo-project/pharo/pull/13449 - Use Compiler not #copyWithTrailerBytes #13488
