[Proposal] List.rotate/4

[Tyler Young]

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 have a rotate algorithm, though it's still somewhat uncommon. I found Dave Abrahams' comments valuable when this was discussed for inclusion in Swift.

I've put together a first draft of an implementation, plus some basic tests.

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.)

[José Valim]

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!

--
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.

[Tyler Young]

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. 🙏

[Wiebe-Marten Wijnja]

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

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/3467969a-8289-42fa-9b4e-741a26da3e1en%40googlegroups.com.

[José Valim]

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).

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/990c93ec-0f9f-0d8a-4d51-731821ebf205%40resilia.nl.

[Tyler Young]

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.

[w...@resilia.nl]

> 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

[José Valim]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/7657048f-da6d-475e-8c43-cb22f22e2e0cn%40googlegroups.com.

[w...@resilia.nl]

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...

[José Valim]

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.

--

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.

[Zach Daniel]

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.

[Tyler]

In the draft implementation on my GitHub, 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

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.

[Tyler Young]

My draft implementation (and the associated @doc and test suite) 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

[José Valim]

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?

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/dff0982d-3d24-4279-a013-e7f08fb2e5cdn%40googlegroups.com.

[Tyler Young]

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

[José Valim]

> 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. :)

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/cce43976-8c96-4098-b926-06133be5ec24n%40googlegroups.com.

[Tyler Young]

Oh, okay, works for me! 😄

I'll put together an implementation.

[José Valim]

Beautiful!

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/ab1d8450-7a6d-4c9b-a6f0-e839fa9bcc00n%40googlegroups.com.

[Tyler Young]

I've moved my drafted implementation to an enum.ex file, and wherever possible, the tests now cover both the list and generic Enumerable implementation.

If this looks good, should I turn it into a PR to elixir-lang/elixir?

[José Valim]

Yes, please!

A couple notes:

1. Instead of %Range{}, try to use first..last//step exclusively. Use underscore for discarded values.

2. I think the Enum implementation can be made more efficient (this is a guess). You don't need four chunks, only two. It can be a two element tuple to accumulate in reverse: pre and post. The idea is like this:

a. First start reverse accumulating head in pre

b. Then start reverse accumulating rotate_back on pos

c. Then reverse accumulate rotate_forward in pre

d. Then reverse accumulate tail on pos

At the end you can do: :lists.reverse(pre, :lists.reverse(pos)).

3. Use Enum.reduce/3 instead of Enumerable because Enum.reduce/3 has some optimizations and it will be faster if you don't have to halt.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/995ee2f1-b011-44c9-811e-a6da70f92528n%40googlegroups.com.

[Tyler Young]

Thanks so much for the feedback. 🙏  I'll make those tweaks and get a PR up!

[Tyler Young]

PR link for posterity:

https://github.com/elixir-lang/elixir/pull/11349