# [swift-evolution] protocol-oriented integers (take 2)

Dave Abrahams dabrahams at apple.com
Sun Jan 15 11:46:35 CST 2017

```on Sun Jan 15 2017, Rob Mayoff <mayoff-AT-dqd.com> wrote:

> On Sat, Jan 14, 2017 at 7:41 PM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> Oh... you mean that word(at:) itself would be linear, and thus
>> algorithms that iterate the words linearly would be O(N^2)...  yuck.
>>
>
> Couldn't you fix this by replacing `func word(at n: Int) -> UInt` with `var
> words: Sequence<UInt>`, producing the words from least to most significant?

Since Sequence<UInt> isn't actually a valid type and the words are
multipass, it would actually be either

// probably too inefficient
var words: AnyCollection<UInt> {get}

or

// a bit more complexity than I'd like to have for this purpose
associatedtype Words : Collection /*where Iterator.Element == UInt*/
var words: Words {get}

The one algorithm we currently have that uses words generically is
iterating them in reverse order, but I think that's easily
solvable.

Slightly more concerning is that word(at:) was designed so that
algorithms could index beyond countRepresentedWords and get a
mathematically correct answer.  So we'd need to either:

1. give that up - not a bad choice considering that it currently
forces a branch into word(at:) that will (probably?) never be used
if the algorithm is written in the most efficient possible way

2. keep countRepresentedWords and make words an infinite collection

I guess I'm leaning towards #1.  Exchanging
countRepresentedWords/word(at:) for Words/words is almost an even trade
in overall complexity.

--
-Dave
```