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

[Dave Abrahams]

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