[Swift-devel] Standard Library Proposal/Discussion Page

[Tim Armstrong]

I think the ideal scenario might be if we could have these in the standard
library, but implemented in Swift.

I tried tried to write Swift code for the min/max problem and it's really
revealing some weird interactions/limitations around the sparse arrays and
iteration constructs provided.

The thing is that there's no straightforward way to iterate in order over
the set of keys in an array, passing a variable from one iteration to the
next.  My thought process was:

   1. Iterate over array with foreach -> doesn't work, since we can't pass
   the max from one iteration to the next
   2. Sequentially iterate over 0..size(A)-1 with for loop -> doesn't work
   since keys may be sparse or not start at 0
   3. Fetch the list of keys and iterate over them with foreach -> doesn't
   work, since foreach doesn't let us pass max from one iteration to the next
   4. Fetch the list of keys, and since we can assume that they're dense,
   iterate over 0..size(A) -1 with a for loop, lookup A[keys[i]], and update
   the max based on that.

So there is a solution, but it's really ugly - I don't think we should have
to create a copy of the array's keys and do a double indirection just to
calculate min/max.  It also feels a little clunky that the eventual
solution depends on implicit contracts about whether an array's keys are
dense or not.

We'd have to assume that most users would give up after #1 or #2.  Also
Swift/K doesn't support for loops, so you have to resort to using arrays.
It's also error prone since many users will neglect to consider that there
may be gaps in the array's key space.

I think there's an issue that there is no direct way to get the first item
in an array, and no direct way to get the successor to an item in the
array.  head/tail is one solution to that, but seems more natural with
linked lists than arrays, since the tail operation sort of implies a copy
of the array, and the tailed array has to support every operation a normal
array supports.  Supporting iterators over the array might be a good
alternative.

So I have a couple of proposals:

   1. Support iterators.  e.g. it = iterator(A); it2 = next(it).
   2. Support sequential foreach with some accumulator variables passed
   between iterations.  This would likely be implemented with iterators.

Supporting ordered iterators in Swift/T would require work, since we store
Swift arrays in hash tables and use string keys, wihch presents two
problems for finding the next integer value after the current one.

- Tim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20150121/0529a2d8/attachment.html>