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

[Xiaodi Wu]

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...


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