Beautiful! On Sun, Oct 24, 2021 at 8:59 PM Tyler Young <s3c...@gmail.com> wrote:
> > Oh, okay, works for me! 😄 > > I'll put together an implementation. > > On Sunday, October 24, 2021 at 1:59:00 PM UTC-5 José Valim wrote: > >> > Re: an Enum version, I'm of the opinion this isn't desirable. It'd be >> useful for ranges, but downright dangerous for other Enumerable types that >> don't have a concept of ordering. E.g., if you wrote some code to do a >> rotate on a map or set, and by some miracle it does what you wanted, you're >> implicitly depending on the exact hashing algorithm used under the hood, >> and the next release could very well break your code. >> >> Yes but this has never stopped us from adding functions to Enum. See >> take/drop, that all assume order. So that should not be a blocker for >> adding rotate. :) >> >> On Sun, Oct 24, 2021 at 8:57 PM Tyler Young <s3c...@gmail.com> wrote: >> >>> I went ahead and pushed a change to make it only accept a step size of 1 >>> (raising an ArgumentError like Enum.slice/2 otherwise). 👍 >>> >>> Re: an Enum version, I'm of the opinion this isn't desirable. It'd be >>> useful for ranges, but downright dangerous for other Enumerable types that >>> don't have a concept of ordering. E.g., if you wrote some code to do a >>> rotate on a map or set, and by some miracle it does what you wanted, you're >>> implicitly depending on the exact hashing algorithm used under the hood, >>> and the next release could very well break your code. >>> >>> It'd be useful if we had a protocol that could express "I'm an *ordered* >>> enumerable," but failing that, I think the potential confusion of rotating >>> on unordered enumerables is worse than the added value of supporting ranges >>> via the Enum module. >>> >>> -- >>> Tyler Young >>> >>> On Wednesday, October 20, 2021 at 10:37:31 AM UTC-5 José Valim wrote: >>> >>>> Great job! >>>> >>>> I think you can simplify this to require ranges to always have a step >>>> of 1. So decreasing ranges will need an explicit //1. We want to do this >>>> for slice, but we can't yet because of backwards compatibility. >>>> >>>> If we have a plan to add this to Enum, then we should add it to Enum >>>> now, to avoid a deprecation down the road. We can postpone a Stream >>>> implementation though (which would be far from trivial). We can however use >>>> the current list implementation to optimize lists rotate. >>>> >>>> For enums, I think it can be done with a single reduce? >>>> >>>> On Wed, Oct 20, 2021 at 5:02 PM Tyler Young <s3c...@gmail.com> wrote: >>>> >>>>> My draft implementation >>>>> <https://github.com/s3cur3/elixir-xutil/blob/main/lib/x_util/list.ex> (and >>>>> the associated @doc and test suite >>>>> <https://github.com/s3cur3/elixir-xutil/blob/main/test/list_test.exs>) >>>>> has been updated to match the range semantics of Enum.slice/2. Among other >>>>> things, that means it has support for negative indices. >>>>> >>>>> I thiiiiiiiink this represents a minimal shippable version of a >>>>> list-only implementation (assuming we're okay with the name, and we're >>>>> okay >>>>> with making it list-only for the time being). >>>>> >>>>> I'd love to get some feedback on what the next steps should be. 🙏 >>>>> >>>>> -- >>>>> Tyler Young >>>>> >>>>> On Sunday, September 5, 2021 at 7:38:19 PM UTC-6 Tyler Young wrote: >>>>> >>>>>> In the draft implementation on my GitHub >>>>>> <https://github.com/s3cur3/elixir-xutil/blob/main/lib/x_util/list.ex>, >>>>>> I've: >>>>>> >>>>>> 1. Changed the implementation to the recursive version >>>>>> (thanks José!). After a bunch of benchmarking and tweaking, this is >>>>>> the >>>>>> fastest version I could come up with on a range of sizes from 16 to >>>>>> 16,384. >>>>>> The recursive one is between 2 and 6% faster at worst; it's something >>>>>> like >>>>>> 40% faster at best. (Happy to supply the benchmarking code if folks >>>>>> are >>>>>> interested.) >>>>>> 2. Implemented the single-element move suggested by Zach Daniel >>>>>> >>>>>> >>>>>> I've not yet added support for negative indices, but it's on my list. >>>>>> >>>>>> Re: naming, I think I agree that slide is a more intuitive name; the >>>>>> only thing I'd say in favor of rotate is that it appears to be the more >>>>>> common name for algorithms that look vaguely like this in other >>>>>> languages. >>>>>> In terms of prior art, I haven't been able to find any languages that >>>>>> call >>>>>> it slide. (That could be a failing of my search skills, though!) >>>>>> >>>>>> Re: supporting any enumerable, my reasoning for proposing it on List >>>>>> rather Enum was specifically to avoid folks confusedly trying to index >>>>>> into >>>>>> Map and MapSet. It'd be easy enough to provide one (ever-so-slightly >>>>>> faster) specialization for lists and one for other enumerables, though. >>>>>> >>>>>> Re: streams, I don't know much about streams in Elixir, but I could >>>>>> take a crack at implementing it. >>>>>> >>>>>> -- >>>>>> Tyler Young >>>>>> >>>>>> >>>>>> On Sat, Sep 4, 2021 at 6:22 PM Zach Daniel <zachary....@gmail.com> >>>>>> wrote: >>>>>> >>>>>>> >>>>>>> Fwiw, “slide” sounds like a much more intuitive name than rotate, to >>>>>>> me. Rotate sounds like a 2d matrix operation (often commonly done on >>>>>>> lists). Additionally, we should probably support a range *or* an index >>>>>>> as >>>>>>> the second argument, since moving one thing is still useful, and would >>>>>>> be a >>>>>>> good first example in the docs. >>>>>>> On Saturday, September 4, 2021 at 2:04:31 PM UTC-4 José Valim wrote: >>>>>>> >>>>>>>> Well, for a stream you are still traversing everything, then I >>>>>>>> guess it makes sense to be linear. I guess the benefit is not having to >>>>>>>> allocate a new data structure. Once again we will need two algorithms, >>>>>>>> depending if the end is before or after start. If before, you need to >>>>>>>> accumulate until you find the slice, then you emit the slice, emit the >>>>>>>> accumulator, and then continue as usual. If after, you need to emit >>>>>>>> everything, until start, then accumulate the slice, and emit >>>>>>>> everything as >>>>>>>> necessary. So both operations will require you to buffer, the amount of >>>>>>>> buffered content depends on the end position. >>>>>>>> >>>>>>>> On Sat, Sep 4, 2021 at 7:34 PM w...@resilia.nl <w...@resilia.nl> >>>>>>>> wrote: >>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> On Saturday, September 4, 2021 at 7:21:45 PM UTC+2 José Valim >>>>>>>>> wrote: >>>>>>>>> >>>>>>>>>> It could definitely be implemented as a Enum or a Stream >>>>>>>>>> function, but the level of complexity is definitely much higher, and >>>>>>>>>> reduce >>>>>>>>>> would force the implementation to be linear anyway. So I am honestly >>>>>>>>>> not >>>>>>>>>> sure if it is worth it. >>>>>>>>>> >>>>>>>>> >>>>>>>>> The main part of the algorithm could be written using a couple of >>>>>>>>> calls to `Enum(erable).slice`. In this case, at least as long as the >>>>>>>>> number >>>>>>>>> of elements to be moved is small, the implementation is faster than >>>>>>>>> linear >>>>>>>>> (for types that support faster than linear slicing). >>>>>>>>> >>>>>>>>> That is, until we concatenate the results at the end to form the >>>>>>>>> rotated list. So at most it is an efficiency improvement of a constant >>>>>>>>> factor, but the result will still be linear. >>>>>>>>> Hmm... >>>>>>>>> >>>>>>>>> -- >>>>>>>>> >>>>>>>> You received this message because you are subscribed to the Google >>>>>>>>> Groups "elixir-lang-core" group. >>>>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>>>> send an email to elixir-lang-co...@googlegroups.com. >>>>>>>>> >>>>>>>> To view this discussion on the web visit >>>>>>>>> https://groups.google.com/d/msgid/elixir-lang-core/d54e1e48-a32c-4d9c-8307-d5cb7926050cn%40googlegroups.com >>>>>>>>> <https://groups.google.com/d/msgid/elixir-lang-core/d54e1e48-a32c-4d9c-8307-d5cb7926050cn%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>>>>>> . >>>>>>>>> >>>>>>>> -- >>>>>>> >>>>>> You received this message because you are subscribed to a topic in >>>>>>> the Google Groups "elixir-lang-core" group. >>>>>>> To unsubscribe from this topic, visit >>>>>>> https://groups.google.com/d/topic/elixir-lang-core/LYmkUopaWN4/unsubscribe >>>>>>> . >>>>>>> To unsubscribe from this group and all its topics, send an email to >>>>>>> elixir-lang-co...@googlegroups.com. >>>>>>> To view this discussion on the web visit >>>>>>> https://groups.google.com/d/msgid/elixir-lang-core/8903e169-dadc-48bf-98ea-f860f1bc0891n%40googlegroups.com >>>>>>> <https://groups.google.com/d/msgid/elixir-lang-core/8903e169-dadc-48bf-98ea-f860f1bc0891n%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>>>> . >>>>>>> >>>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "elixir-lang-core" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to elixir-lang-co...@googlegroups.com. >>>>> >>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msgid/elixir-lang-core/dff0982d-3d24-4279-a013-e7f08fb2e5cdn%40googlegroups.com >>>>> <https://groups.google.com/d/msgid/elixir-lang-core/dff0982d-3d24-4279-a013-e7f08fb2e5cdn%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>> . >>>>> >>>> -- >>> You received this message because you are subscribed to the Google >>> Groups "elixir-lang-core" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to elixir-lang-co...@googlegroups.com. >>> >> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/elixir-lang-core/cce43976-8c96-4098-b926-06133be5ec24n%40googlegroups.com >>> <https://groups.google.com/d/msgid/elixir-lang-core/cce43976-8c96-4098-b926-06133be5ec24n%40googlegroups.com?utm_medium=email&utm_source=footer> >>> . >>> >> -- > You received this message because you are subscribed to the Google Groups > "elixir-lang-core" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to elixir-lang-core+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/elixir-lang-core/ab1d8450-7a6d-4c9b-a6f0-e839fa9bcc00n%40googlegroups.com > <https://groups.google.com/d/msgid/elixir-lang-core/ab1d8450-7a6d-4c9b-a6f0-e839fa9bcc00n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "elixir-lang-core" group. To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4KRqMVh4xev84mV9PughE2ShsdL66cvw4pWWu9fpTx1og%40mail.gmail.com.
