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-core+unsubscr...@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/CAGnRm4L8UB12Uqg_Pg5mhAtr%2B54CKuiOpVF8T%3DunGk4qRzrT3g%40mail.gmail.com.
