[swift-evolution] Representation of natural numbers with a distinct type
David Turnbull
dturnbull at gmail.com
Wed Feb 3 19:08:41 CST 2016
Here's how you could use a collection as a predicate. The OnSwitchesIndex is
opaque to anything outside the file. There's no way to iterate OnSwitches with
0 ..<count. Thinking that arrays and sequences are counting up from 0 by 1
is missing the entire point of these protocols.
class Switches : CollectionType{
private let data:[Bool]
init(_ d:[Bool]) {
data = d
}
var startIndex: Int {
return data.startIndex
}
var endIndex: Int {
return data.endIndex
}
subscript(i:Int) -> Bool {
return data[i]
}
}
struct OnSwitchesIndex : ForwardIndexType {
private let data:Switches
private let index:Int
init(_ d:Switches, _ i:Int) {
data = d
for i in i..<data.endIndex {
if data[i] {
index = i
return
}
}
index = data.endIndex
}
func successor() -> OnSwitchesIndex {
return OnSwitchesIndex(data, index+1)
}
}
func ==(lhs: OnSwitchesIndex, rhs: OnSwitchesIndex) -> Bool {
return lhs.index == rhs.index
}
class OnSwitches : CollectionType {
let data:Switches
init(_ d:Switches) {
data = d
}
var startIndex: OnSwitchesIndex {
return OnSwitchesIndex(data, data.startIndex)
}
var endIndex: OnSwitchesIndex {
return OnSwitchesIndex(data, data.endIndex)
}
subscript(sw: OnSwitchesIndex) -> Int {
assert(sw.data.data == data.data)
return sw.index
}
}
let x:Switches = Switches([false, true, true, false, true])
x.count // == 5
let y = OnSwitches(x)
y.count // == 3
for z in y { print(z) } // == prints 1 2 4
-david
On Wed, Feb 3, 2016 at 1:09 PM, James Froggatt <conductator at ntlworld.com>
wrote:
> I'm not sure I follow. Could you elaborate on this?
>
> If such a type were made, I'm fairly sure generic functions designed to
> accept a CollectionType would throw an error if the count were negative (if
> trying to iterate with 0 ..< .count, for example), indicating such a type
> doesn't implement the protocol as it was intended to be used.
>
> From James F
>
> On 3 Feb 2016, at 20:50, David Turnbull <dturnbull at gmail.com> wrote:
>
> You can have a collection with a negative count. There's uses for this
> too. For example, importing data. You can import whatever garbage in one
> pass, and validate in a second. That way you don't have to mix concerns in
> your code.
>
> -david
>
> On Wed, Feb 3, 2016 at 12:35 PM, <davesweeris at mac.com> wrote:
>
>> What about .count? Is it possible for that to be negative? *If* we
>> change how count is represented, I think it should be switched to size_t,
>> rather that UInt. I’m aware that they’re currently the same thing, but that
>> might not always be the case, and, at least the way I understand things,
>> the max value of a platform’s “pointer” type is more directly tied to the
>> maximum possible element count than the max value of its native uint type.
>> I know of at least one platform in development which uses 64 bits for
>> pointers, but the address space is only 61 bits because the CPU & memory
>> system use 3 bits for flags.
>>
>> - Dave Sweeris
>>
>>
>>
>> On Feb 3, 2016, at 11:58, David Turnbull via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>> -1 CollectionType and it's ilk, contrary to what you believe, were
>> designed to handle negative indexes just fine. Or even indexes that aren't
>> numeric. And there's plenty of real use cases for this.
>>
>> class GraphRow : MutableCollectionType {
>> var values = [Int](count: 201, repeatedValue: 0)
>> var startIndex: Int { return -100 }
>> var endIndex: Int { return 100 }
>> subscript(column: Int) -> Int {
>> get {
>> return values[column+100]
>> }
>> set {
>> values[column+100] = newValue
>> }
>> }
>> }
>> var r = GraphRow()
>> r[-3] = 12
>> r[9] = 2
>> print(r[-3])
>> print(r.reduce(0, combine: +))
>>
>> -david
>>
>>
>> On Wed, Feb 3, 2016 at 9:31 AM, James Froggatt via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>>> In the standard library, there are methods (notably array subscripts,
>>> CollectionType's .count and the dimensions of CGSize) which are designed to
>>> deal only with natural (non-negative) numbers. Functions either throw an
>>> error if a parameter is negative, or else ignore the possibility of a
>>> negative value finding its way into these functions.
>>>
>>> By updating the standard library with a natural number type to represent
>>> these values (and potentially the Swift interfaces for Foundation and other
>>> frameworks), there is no way a negative number can be passed to these
>>> functions. This eliminates the need for many preconditions, allowing them
>>> to eliminate the possibility of a crash, and it would be clear that values
>>> such as count will never be negative.
>>>
>>> If this change were accepted, the user would have to explicitly convert
>>> between the types at some points in their code. This could be seen as a
>>> burden, but requiring a cast encourages the programmer to check for
>>> negative values, keeping negatives out of natural number functions, and
>>> moving checks to the source of the data, similar to how Optionals eliminate
>>> nil values early on.
>>>
>>> The parallel to Optionals is, in my opinion, the most appealing aspect
>>> of this idea. With Swift's focus on type safety, the lack of distinction
>>> between natural numbers and potentially negative ones seems like an
>>> omission, given how commonly both kinds of number are used. Enabling this
>>> level of integral safety would add additional clarity and reduce potential
>>> errors. Use cases include not just indexes, but in sizes such as
>>> collections' count and CG dimensions, for both clarity when getting values,
>>> and enforcing valid values at initialisation.
>>>
>>> UInt is the obvious candidate to represent integer natural numbers, but
>>> is hazardous in edge cases: UInt allows an extra bit for magnitude, so has
>>> the possibility of overflow when converting back to Int. I assume this
>>> hazard is the primary reason UInt currently isn't used. If this a concern,
>>> a separate collection of types for natural integers (NInt?) could be
>>> created, which could be a strict subset of the correspondingly sized Int
>>> values (using n-1 bits).
>>>
>>> This would mean adding a new collection of integer types in the standard
>>> library, which is undesirable. However, for high level applications which
>>> Swift is primarily used for, this would arguably be a more useful type than
>>> UInt, considering the near absence of UInt in current APIs, and its tiny
>>> increase (1 bit?) in precision compared to using an Int of a larger size.
>>> An unsigned Integer subset would allow safe conversion back to Int, and the
>>> conversion from Int is relatively simple, from the design perspective -
>>> ignore the sign bit, throw an error, or round up to 0, as appropriate.
>>>
>>> Alternatives include:
>>> • A generic wrapper for Int which constrains its possible values. This
>>> would allow inherent support for use with existing operators, but would be
>>> rather clunky in cases where only natural numbers are being dealt with.
>>> • In a future version of Swift, the addition of type parameters
>>> constraining possible values may enable this to be added, but even if this
>>> does get added it may be too late to make such a major change.
>>> • Leaving the APIs as they are and require every function dealing with
>>> natural numbers to either throw a runtime error when a negative is passed.
>>> If the user forgets to follow this rule (or wont put in the extra effort to
>>> add the check), their functions will have unspecified behaviour.
>>>
>>> This ended up longer than I would like, sorry about that. I don't think
>>> this issue has been covered here.
>>> I'd be interested to hear responses and opinions, and while I'm
>>> confident this change would be beneficial if done correctly, doing it
>>> correctly is easier said that done.
>>>
>>> - James
>>> _______________________________________________
>>> 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
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160203/47a423c4/attachment.html>
More information about the swift-evolution
mailing list