[swift-evolution] Feature proposal: Range operator with step

[Dave Abrahams]

on Mon Mar 28 2016, Xiaodi Wu <swift-evolution at swift.org> wrote:

> Right, Countable could refine Strideable. I'm no expert on this, but
> some cursory reading suggests that the analogous feature in C++ simply
> requires the type to have operator++ defined. Obviously, that won't
> work for Swift 3.0...

Hmm, instead of defining a new protocol (Countable), what if we just use
“Strideable where Stride : Integer” as a constraint?

>
> On Mon, Mar 28, 2016 at 12:19 PM, Dave Abrahams via swift-evolution
> <swift-evolution at swift.org> wrote:
>>
>> on Fri Mar 25 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>
>>> I'd reply inline but I'm working around some technical limitations on
>>> the go here. Agreed that anything countable should be good for a Range
>>> that conforms to Collection. Well, anything finite, maybe.
>>
>> I don't think the domain being finite is important at all.  You have
>> concrete endpoints.
>>
>>> See below about countably infinite ranges.Re hypothetical Countable
>>> protocol:I'm not advocating for another protocol for the numeric
>>> type. I'll take your word for it that they aren't jolly, though I
>>> don't know why.
>>
>> Then I should explain.  I don't want to have both a set of Countable
>> protocols and a set of Collection protocols, each with forward,
>> bidrectional and random-access traversal, the former being able t
>> traverse on their own and the latter being able to traverse via an
>> associated Index.  That would be an unpleasant level of complexity to
>> impose on users.
>>
>>> The issue as I see it is this: currently, Range is documented as a
>>> collection of *discrete* index values.
>>
>> Yes, that would change.
>>
>>> If Intervals are going away, does a Range<Float> model a countable set
>>> of Floats with unit stride, a finite set of Floats in the technical
>>> sense that there exists only a finite set of representable numbers, or
>>> an uncountable set?
>>
>> The latter; we mostly choose to ignore the fact that Floats are not
>> truly arbitrary real numbers, to match most peoples' mental/programming
>> models.  The FloatingPoint protocol will also expose all the operations
>> that let you deal with the fact that they are not arbitrary reals.
>>
>>> The former two preserves the current definition of Range as a
>>> collection of discrete values but may be astonishing to users. But, if
>>> we agree that the last scenario is most intuitive,
>>
>> we do
>>
>>> how then can we make the distinction between a "Range" that represents
>>> an uncountable set of things with an upper and lower bound and one
>>> that represents a countable set of things?
>>
>> It depends on the characteristics of the range's Bound type.  If it's
>> discrete and Countable, you get the latter kind.
>>
>>> Thinking more on this, expanding Range to floating point types opens
>>> you up to another inconsistency. Can the bounds be -inf and inf?
>>
>> Yes.
>>
>>> I don't see why that should be a problem for an Interval, but now
>>> we're in for some trouble if you want it for a Range that can be
>>> strided through.
>>
>> I don't.
>>
>>> How about 0.0 and inf? That makes sense to allow.
>>
>> Yes.
>>
>>> But why should the ranges I'm allowed to specify be constrained by
>>> what makes sense to stride?
>>
>> They are not.
>>
>>> So the more I think about it, the more I'm convinced that the logic
>>> for what Range-Interval hybrids can be strided through can't neatly
>>> accommodate floating point types. If you merge Range and Interval,
>>> I still want to be able to specify
>>> `-Double.infinity..<Double.infinity`. But if I can do that, then
>>> Range<Double> shouldn't even have `striding(by:)`.
>>
>> Right.  I think we're on the same page.  If we had conditional
>> conformances, we'd have
>>
>>   struct Range<T: Comparable>
>>     : HalfOpenRange { ... }
>>
>>   extension Range<T: Comparable where T: Countable>
>>     : HalfOpenRange, Collection { ... }
>>
>> (and the closed-range variants). Until then, we'll need
>>
>>   struct RangeOfCountable<T: Comparable where T: Countable>
>>     : HalfOpenRange, Collection { ... }
>>
>> (and the closed-range variant).
>>
>> The problem is, how to define Countable?  If we had to account for all
>> the different possible traversals, we'd end up with 8 different Range
>> types (3 Countable and 1 uncountable, closed and half-open).  We're
>> already in a similar position with 12 Slice types(!) in the new design.
>>
>> I'm not sure if we can do without that complexity for Slices, but in
>> the case of Ranges, I think it's probably OK to say Countable refines
>> Strideable, because we won't have any models of Countable that don't
>> have random access.
>>
>>> From: Dave Abrahams via swift-evolution <swift-evolution at swift.org>
>>> Sent: Friday, March 25, 2016 8:11 PM Subject: Re: [swift-evolution]
>>> Feature proposal: Range operator with step To:
>>> <swift-evolution at swift.org>
>>>
>> ...<schnipp 19>...
>>> on Fri Mar 25 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>>
>>>> Ah, I think the conceptual muddle arises in the plan
>>>> then. Specifically, I'd argue that not all Ranges with Strideable
>>>> bounds should conform to Collection.
>>>>
>>>> Conceptually, whether a type can be advanced by some distance
>>>> (guaranteed by Strideable) is orthogonal to whether a type has an
>>>> obviously correct increment when calling next() on its iterator. Thus,
>>>> although *strides* with Strideable bounds should obviously conform to
>>>> Collection, Ranges that conform to Collection should be constrained to
>>>> types which imply that the Range represents a countable set (as the
>>>> mathematicians say) of numbers.
>>>
>>> I think any countable set should be OK, regardless of whether the
>>> elements are numbers.  Ranges of UnsafePointers, for example, are
>>> countable.
>>>
>>>> This distinction may come in handy for implementing strides that don't
>>>> accumulate error. Striding through a Range that represents a countable
>>>> set of elements shouldn't accumulate error and we can use what we
>>>> already have--i.e. increment the current value every iteration without
>>>> inspecting the value of the starting bound. Striding through a Range
>>>> that represents an uncountable set of elements definitely requires
>>>> reckoning from the starting bound every iteration.
>>>
>>> So, what does this Countable protocol look like?  It seems like it would
>>> bring back the Index protocols that are otherwise obviated by this
>>> plan... not a jolly prospect.
>>
>> --
>> Dave
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
Dave