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-core+unsubscr...@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.
