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

[Nate Cook]

> On May 6, 2016, at 3:18 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> on Thu May 05 2016, Nate Cook <swift-evolution at swift.org <mailto: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?

I mean looping count / 2 times instead of looping while lowIndex < highIndex, not a fixed number of iterations for every array.

>>> 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
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160506/f7fb5661/attachment.html>