Ahh, I see what you're saying, José. Yeah, under the List.rotate(list, range, index) model, your range could be negative independently of the insertion index.
Re: the efficiency issues, as Chris Keathley puts it less diplomatically, "lists are a garbage data structure." 😂 But given that so much of the ecosystem is already built on lists, and we already have lots of linear-time algorithms on them, I don't feel like this *adds* to the problem. If anything, you'd be reaching for this when the alternative is to do the split-and-recombine by hand. At least with a standard library implementation, we could provide the safest, cleanest implementation possible. On Thursday, September 2, 2021 at 9:57:06 AM UTC-5 José Valim wrote: > 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 <[email protected]> > 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 <[email protected]> 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 [email protected]. >>>> 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 [email protected]. >> 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 [email protected]. >> > 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/de8f578a-f6b3-4dc5-acd7-5c166b45b920n%40googlegroups.com.
