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.
On Sat, Sep 4, 2021 at 7:07 PM w...@resilia.nl <w...@resilia.nl> wrote: > > 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). > > Interestingly, moving a small slice a small distance will probably be much > faster on an array (because both lookup and replacement of individual > values at arbitrary locations in the array is faster). However, if we are > moving, say, the first element to the end, then arrays and lists will both > be roughly equally expensive because all elements will need to be moved > around. > > > 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. > > Agreed! > If we clearly document this, it should definitely be fine 👍. > > One more question: > Do we want to add this to `List`, or rather to `Enum`? > Other enumerables besides lists‡ might benefit from this. And having it > available as a lazy function in `Stream` might also be beneficial. > > ‡: Any enumerable where element ordering is important. Essentially > anything except maps and `MapSet`s. > > ~Marten/Qqwy > On Thursday, September 2, 2021 at 5:07:50 PM UTC+2 s3c...@gmail.com wrote: > >> 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 <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-co...@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-co...@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/7657048f-da6d-475e-8c43-cb22f22e2e0cn%40googlegroups.com > <https://groups.google.com/d/msgid/elixir-lang-core/7657048f-da6d-475e-8c43-cb22f22e2e0cn%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/CAGnRm4%2BtH72_L0M55vynyCwYxTyQ05iqbuKdXUvoSZhvvNnROg%40mail.gmail.com.
