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/c07ce378-5512-4074-9480-9eefc7b3b8d4n%40googlegroups.com.
