[Swift-devel] Associative array in Swift [GSoC]

[Mihael Hategan]

On Tue, 2011-06-21 at 11:11 +0200, Ben Clifford wrote:
> On Jun 20, 2011, at 11:44 AM, Mihael Hategan wrote:
> 
> > That's some crappy writing, but if I'm reading it right  and in haskell
> > lingo:
> > 
> > map_ ::  (Tk1 Tv1) -> [(Tk2, Tv2)]
> > There is an automatic collect_:: [(Tk2, Tv2)] -> (Map Tk2 [Tv2])
> > reduce_ :: (Tk2 [Tv2]) -> [Tv3]
> > 
> > There's an input: (Map Tk1 Tv1) and the system does:
> > intermediate = map (map_) toList input
> > result = foldl (++) [] map (reduce_) toList collect_ intermediate
> > 
> > So it does seem like the shapes of the arrays can depend in non-trivial
> > ways on the algorithm.
> 
> the above looks ok. I think swift arrays can pretty much handle the
> shapes of array needed. When Tk1 and Tk2, the key types of the input
> data and intermediate data, are numeric, then swift already has that.

Right. I'm saying though that I see where Yadu's and Justin's assessment
about the need for an array append mechanism is coming from.

But then, on a second thought, since we don't care about indices, then
we could do (and I'm taking some liberties there with explicitly
specifying array key types):
type T2 {
  Tk2 k; Tv2 v;
}

(Tv2 r[Tk2][]) collect(T2 input[]) {
  foreach v, i in input {
    r[v.k][i] = v.v;
  }
}

type Tk3 {
  Tk2 k1;
  int k2;
}

(Tv3 r[Tk3]) reduce(Tv2 i[Tk2][]) {
  foreach v2array, k in i {
    x = reduce_(k, v2array);
    foreach y, j in x {
      Tk3 k3; k3.k1 = k; k3.k2 = j;
      r[k3] = y;
    }
  }
}

We can probably do without arbitrary typed keys if all TkX are int, but
in the case of word counting (see below), that won't quite be the case.

> 
> But what would a whole map-reduce like program look like in Swift?
> Trying to write out a (non-contrived) example of "this is the program
> that I think I should be able to write, even though Swift can't run it
> today" would be interesting, perhaps. I found that very interesting
> when arguing how while loops were useless in Swift all those years
> ago, and I think there are some interesting issues waiting to be
> discovered around how you would actually implement a useful map body
> and reduce body.

I think the typical example (if I remember correctly) used in the
map/reduce paper is a reasonable case: count the number of occurrences
of each word in a set of files.

In a sense, this can be easy if we don't insist that this be implemented
in the exact same way as with m/r. The one can say something along the
lines of:

result = uniq(sort(cat(map(count_words, files)))) (of course, with map
being a  foreach and so on).

But if we need a collect() with the same semantics as the one in m/r,
then it's a bit of a different story I think.