PR link for posterity:
https://github.com/elixir-lang/elixir/pull/11349
On Monday, October 25, 2021 at 7:02:08 AM UTC-5 Tyler Young wrote:
> Thanks so much for the feedback. 🙏 I'll make those tweaks and get a PR
> up!
>
> On Monday, October 25, 2021 at 6:59:45 AM UTC-5 José Valim wrote:
>
>> 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.
>>
>> On Mon, Oct 25, 2021 at 1:40 PM Tyler Young <[email protected]> wrote:
>>
>>> 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
>>>
>>> <https://groups.google.com/d/msgid/elixir-lang-core/995ee2f1-b011-44c9-811e-a6da70f92528n%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/fdca39c8-c03a-49d9-aebb-5f2178ec311dn%40googlegroups.com.
