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

[Dave Abrahams]

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?


Yeah... I thought about that...

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