[Swift-devel] Standard Library Proposal/Discussion Page

[Mihael Hategan]

I think this is a general problem with Swift: the inability to have
accumulator variables. It leads to the necessity to use recursion, but
that isn't in itself enough because of the issue with tail(array) that
you mention. So iterators seem like the right choice there.

You mentioned non-sparse arrays. The only problem with algorithms based
on dense arrays is that they might not be very efficient in swift since
elements are not necessarily generated in order. It may just be that
a[0] will make it into the array last due to parallelism.

So I think updateables > iterators > dense arrays > tail > nothing.

The question is whether we would design the standard library differently
if we had either of updateables or iterators vs. what we have right now
(nothing) and whether the differences would be significant enough for us
to suspend the standard library discussion until we have these features.

Mihael

On Wed, 2015-01-21 at 09:14 -0600, Tim Armstrong wrote:
> 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