Hi Richard, That sounds great. I am looking forward to playing with it.
Bernhard > Am 25.04.2023 um 04:11 schrieb Richard O'Keefe <rao...@gmail.com>: > > 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](http://vivaldi.com/) herunter
