I've moved my drafted implementation to an enum.ex <https://github.com/s3cur3/elixir-xutil/blob/main/lib/x_util/enum.ex#L31> file, and wherever possible, the tests <https://github.com/s3cur3/elixir-xutil/blob/main/test/enum_test.exs> now cover both the list and generic Enumerable implementation.
If this looks good, should I turn it into a PR to elixir-lang/elixir? On Sunday, October 24, 2021 at 2:06:45 PM UTC-5 José Valim wrote: > Beautiful! > > On Sun, Oct 24, 2021 at 8:59 PM Tyler Young <[email protected]> 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 <[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 >> >> <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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/995ee2f1-b011-44c9-811e-a6da70f92528n%40googlegroups.com.
