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 <bernh...@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 <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 >> herunter >> > >
