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

[Mihael Hategan]

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.



On Mon, 2011-06-20 at 09:02 +0100, Ben Clifford wrote:
> On Jun 19, 2011, at 9:18 AM, Mihael Hategan wrote:
> 
> > But looking back at the initial email, I think that we should dig into
> > the assumptions that prompted this discussion. There has been a lot of
> > talking on how to do this, but almost nothing on why we should do it.
> 
> My understanding is its the "collect all pairs with same key" bit of the below wikipedia quote. It seems superficially to look quite nice, but I'd be interested in seeing what the reduce bit would look like.
> 
> ===== http://en.wikipedia.org/wiki/MapReduce#Logical_view
> The Map and Reduce functions of MapReduce are both defined with respect to data structured in (key, value) pairs. Map takes one pair of data with a type in one data domain, and returns a list of pairs in a different domain:
> Map(k1,v1) → list(k2,v2)
> The Map function is applied in parallel to every item in the input dataset. This produces a list of (k2,v2) pairs for each call. After that, the MapReduce framework collects all pairs with the same key from all lists and groups them together, thus creating one group for each one of the different generated keys.
> The Reduce function is then applied in parallel to each group, which in turn produces a collection of values in the same domain:
> Reduce(k2, list (v2)) → list(v3)
> Each Reduce call typically produces either one value v3 or an empty return, though one call is allowed to return more than one value. The returns of all calls are collected as the desired result list.
> ====