There is a much newer version. I've made some minor corrections today. I really must put it up on github. Let me get back to you about that. On Sat, 22 Apr 2023 at 18:57, Bernhard Pieber <bernhard@pieber.com> wrote:
Hi Richard,
I really liked your concise description about what is the point of using an object-oriented language. It made my day.
I searched the Web for your Smalltalk library and found this link: http://www.cs.otago.ac.nz/staffpriv/ok/astc-1711.tar.gz
Is there a newer version available somewhere?
Cheers, Bernhard
Am 22.04.2023 um 00:51 schrieb Richard O'Keefe <raoknz@gmail.com>:
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 <merkste@web.de> 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 <merkste@web.de> wrote:
Dear Richard,
thanks for that additional piece. I'll put insert-<left/right> 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