[swift-evolution] [Review] SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++

[Dave Abrahams]

on Thu May 05 2016, Nate Cook <swift-evolution at swift.org> wrote:

> Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.
>
>> On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr at gmail.com> wrote:
>> 
>> On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution
>> <swift-evolution at swift.org> wrote:
>>> Hello Swift community,
>>> 
>>> The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.
>> 
>> Hi,
>> 
>> I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
>> myself.  We met and discussed the proposal in great detail.
>> 
>> First of all, we want to thank Nate and Sergey for proposing this API,
>> which is an important and useful algorithm.  We are generally in favor
>> of the proposal, but we would like to request a few changes.
>> 
>> Could you make 'func rotate' a requirement in the MutableCollection
>> protocol?  This allows selecting the best implementation for a given
>> concrete type, even when calling from generic code.
>> 
>> Could you explain why do we need a special implementation of
>> 'reverse()' for RandomAccessCollection?  We couldn't think of a
>> performance reason for this.
>
> With a bidirectional collection, you have to compare the high and low
> index at each iteration, stopping when low >= high (before indices
> were Comparable, this required two equality comparisons per
> iteration). With a random-access collection, you can optimize the loop
> to use a fixed number of iterations, which should be more efficient.

How can you reverse a variable-length collection with a fixed number of
iterations?  Are you talking about loop unrolling in the library?

>
>
>> Could you add complexity clauses to all new documentation comments?
>> 
>> We have discussed the names for these functions at length.  We felt
>> like the argument in 'rotate(firstFrom:)' does not convey the
>> argument's role well.  Our suggestion is to use
>> 'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'.  These
>> names emphasize that methods operate on the whole collection, shifting
>> all elements.  The argument is the index of the element that is moved
>> to the start index, and we tried to convey that by using the word
>> 'start' instead of 'first'.  In the standard library, 'first' refers
>> to the element itself, not the index.  Indices use 'startIndex' and
>> 'endIndex'.
>> 
>> We have considered a lot of alternative names, including
>> 'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'
>> and others, but they were not as good.  The problems are:
>> 
>> - 'swapSubranges' is mostly good, but 'subranges' does not imply that
>> the two subranges cover the whole collection.  The user might
>> reasonably expect to pass two subranges that will be swapped.
>> 
>> - 'Half' implies that two parts make a whole, but it also implies that
>> two parts are of equal size, which is not the case for this API.
>> 
>> - 'splitAndSwap' implies that we are operating on the whole, but feels
>> a very roundabout way to describe the operation.
>
> Agreed on all of this. The rotate name is hard to beat!
>
>> For a non-mutating rotation we suggest defining separate types,
>> RotatedCollection, RotatedBidirectionalCollection, and
>> RotatedRandomAccessCollection, instead of returning a
>> FlattenCollection.  This has a few advantages.
>> 
>> - We can change the non-mutating 'rotated()' to just return the
>> collection instead of returning tuples of the collection and the
>> index.  The index of the former first element can be stored inside the
>> RotatedCollection in a property.  This change allows easier chaining
>> on '.rotated()', and goes in line with the return value of the
>> mutating 'rotate()' being discardable.
>> 
>> - Using an array in the return type of 'rotated()'
>> (FlattenCollection<[Self.SubSequence]>) would be less efficient than
>> it could be (extra allocation), and also feels like exposing too many
>> implementation details that we might want to change in future (for
>> example, if we get a CollectionOfTwo type).
>> 
>> - In future, when we have conditional protocol conformances in the
>> language, we would fold the three RotatedCollection types into one
>> type that conditionally conforms to collection protocols based on the
>> capabilities of the underlying collection.  We won't be able to do
>> that if some overloads return a FlattenCollection.
>> 
>> For lazy 'rotated()', just like for non-mutating 'rotated()', we
>> recommend returning only one value, a LazyCollection that wraps an
>> appropriate RotatedCollection.  The RotatedCollection will store the
>> index of the former first element in a property.
>> 
>> Dmitri
>> 
>> -- 
>> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
>> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
Dave