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/CAGnRm4%2B5WKn7H7ZZd-w%3D7PotsakRfefkuroJvbrhppqHnnBvQw%40mail.gmail.com.
