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 <[email protected]> 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 <[email protected]> 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 <[email protected]> >>>>> 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 [email protected] <[email protected]> >>>>>>> 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 [email protected]. >>>>>>>> >>>>>>> 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 >>>>>> [email protected]. >>>>>> 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 [email protected]. >>>> >>> 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 [email protected]. >> > 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/ab1d8450-7a6d-4c9b-a6f0-e839fa9bcc00n%40googlegroups.com.
