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 <rao...@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 <merk...@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 <merk...@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](http://vivaldi.com/) herunter
