I don't think there is any restriction on the end. It can be anywhere on the list. The semantics for start..middle can be designed based on Enum.slice/2 and the semantics of "end" on insert_at. After all, List.rotate seems to be a "slice" plus a "insert_many_at". Although end should never fall within start..middle (we should raise for those cases).
The other thing is that the implementation can be made more efficient if we take the end into account. For example, if end is after middle, we can use a non-tail recursive to start traverse until we find the start: def find_start(list, 0), do: accumulate_start_middle(list, middle, end, []) def find_start([h | t], start, middle, end), do: [h | find_start(t, start - 1, middle, end)] Then accumulate_start_middle will get all values from start to middle and accumulate them in a list in reverse order. Then you need to find end, using a non-tail recursive approach and reverse the accumulator into the rest: def find_end(rest, 0, acc), do: Enum.reverse(acc, rest) def find_end([h | t], end, acc), do: [h | find_end(t, end - 1, acc)] This guarantees the list is only copied once (plus one additional copy for the start..middle slice). A similar approach can be devised if the end is before the start. --- Wiebe-Marten Wijnja, unfortunately I think those operations would be relatively expensive on an array too, in terms of mutations, although the index lookup is faster. As other function in the List module, I think we should document that they would be very expensive in a loop (but ok as one-offs). On Thu, Sep 2, 2021 at 4:10 PM Wiebe-Marten Wijnja <w...@resilia.nl> wrote: > Playing devil's advocate here for a second: > We are talking about a situation where you have a collection of items, and > you want to add elements to the middle/remove elements from the > middle/reorder elements into the middle. > > I do not think that lists are the right tool for this job here, as these > operations will slow down significantly when the list grows in size. > As such, maybe adding such an operation to the `List` module might not be > such a good idea, as we will be giving new developers a tool which they may > hurt themselves with, > rather than choosing a data structure (like another array collection, such > as map-based arrays or `:array`) that fits the requirements better. > > ~Marten/Qqwy > On 02-09-2021 15:40, Tyler Young wrote: > > Thanks so much for the feedback, José. ☺️ > > 1. My working model was that all indices should be in the range [0, length > - 1]. I could imagine supporting either 3x non-negative or 3x negative > indices (with negative indices offsetting from the end of the list as > usual). I'm not sure whether the negative version would be more confusing > than it's worth, though. > 2. If the middle index is equal to the start index, you're essentially > asking to move the range between indices n and m to start at... index n, so > you'll get the list back unchanged. For middle less than start, I think > we'd want to consider that a contract violation, and return the original > unchanged. > 3. I'd suggest making the contract (in the form of the docs, I suppose) > specify start <= middle <= end, and any violation of that gives you back > the original list. (I thiiiiiink that's consistent with the existing design > of List—e.g., List.pop_at/3 returns the original list if you give it an > index that's off the end, rather than raising an error or something. > 4. Oooh, I like that a lot. That helps a lot with deciphering which > parameters are which. 🙏 > > On Thursday, September 2, 2021 at 4:31:18 AM UTC-5 José Valim wrote: > >> Hi Tyler! I think starting with a basic List.rotate is very welcome. My >> questions are: >> >> 1. Which of those indexes can be negative? >> 2. What happens if the middle index is less than or equal to the start >> index? >> 3. What happens if the last index is within start and middle? >> 4. Could List.rotate(list, range, index) be a better API? I.e. move the >> list represented by indexes in range to index? >> >> Thanks for the proposal! >> >> On Thu, Sep 2, 2021 at 3:38 AM Tyler Young <s3c...@gmail.com> wrote: >> >>> Hi folks! >>> >>> I'd like to propose a List.rotate/4 function (and maybe some >>> convenience wrappers for it as well). >>> >>> Rotate is one of those algorithms that, once I learned about it, I >>> started seeing it everywhere. It's somewhat complicated to grasp (it takes >>> 4 parameters, after all), but in situations where you need it, it's still >>> *much* simpler than the equivalent imperative version. >>> >>> The classic use case is this: Suppose you have a list of to-do items, >>> which the user has ordered by priority: >>> >>> 1. Apply to college >>> 2. Brush the dog >>> 3. Change the car's oil >>> 4. Deliver flowers >>> 5. Exchange gifts >>> >>> A "rotate" or "slide" occurs when the user selects some number of >>> elements and drags them to a new place in the list. Let's say they selected >>> items 3 & 4 from the preceding and dragged them above item 2. When they >>> release the mouse, the new order should be: >>> >>> 1. Apply to college >>> 2. Change the car's oil >>> 3. Deliver flowers >>> 4. Brush the dog >>> 5. Exchange gifts >>> >>> Doing this without the named algorithm requires 3 splits (one at the >>> insertion point, one at the start of the selected range, and one at the end >>> of the selected range). It's easy to get the index math wrong, and it's >>> even harder for readers of your code to grasp what's going on. Adding this >>> as a "vocabulary" algorithm would help a lot, I feel. >>> >>> A number of other languages >>> <https://twitter.com/code_report/status/1419900906062204939?s=20> have >>> a rotate algorithm, though it's still somewhat uncommon. I found Dave >>> Abrahams' comments >>> <https://forums.swift.org/t/proposal-implement-a-rotate-algorithm-equivalent-to-std-rotate-in-c/491/2> >>> valuable when this was discussed for inclusion in Swift. >>> >>> I've put together a first draft of an implementation >>> <https://github.com/s3cur3/elixir-xutil/blob/main/lib/x_util/list.ex>, >>> plus some basic tests >>> <https://github.com/s3cur3/elixir-xutil/blob/main/test/list_test.exs>. >>> >>> If this is something folks decide we want, it might also be worth >>> considering a few variants (also implemented in the file linked above): >>> >>> - slide/4: Syntactic sugar over rotate, but it's useful in practice >>> because usages of rotate often need to be able to move a chunk of the >>> list >>> either or backward. (Most usages I've seen in the wild end up doing an if >>> insertion_idx < range_start . . . else . . .) >>> - slide_one/3, where the second argument is the index of the single >>> element to move and the last argument the target index. This would just >>> be >>> syntactic sugar over slide/4. (In my experience, about half the >>> times I use this algorithm, the conceptual requirements guarantee that >>> it'll only act on a single element.) >>> >>> -- >>> 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/01c63660-6a11-4e69-bdcb-6659579ef683n%40googlegroups.com >>> <https://groups.google.com/d/msgid/elixir-lang-core/01c63660-6a11-4e69-bdcb-6659579ef683n%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/3467969a-8289-42fa-9b4e-741a26da3e1en%40googlegroups.com > <https://groups.google.com/d/msgid/elixir-lang-core/3467969a-8289-42fa-9b4e-741a26da3e1en%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/990c93ec-0f9f-0d8a-4d51-731821ebf205%40resilia.nl > <https://groups.google.com/d/msgid/elixir-lang-core/990c93ec-0f9f-0d8a-4d51-731821ebf205%40resilia.nl?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/CAGnRm4LHs9%3DiXMx5V%2ByLsKMQwtHRQmcce5sZNNW9%3DzezFaRbxg%40mail.gmail.com.
