Re: Sort Associative Array by Key

```On Tuesday, 27 August 2019 at 16:25:00 UTC, Samir wrote:
```
As I've mentioned on the list before, I really struggle to understand how some of the std.algorithm functions such as `map` work when combined with things like `array`, `sort` and especially `zip` but really appreciate the support I find here on the forum.
```
```
A few months ago I stuggled with that too. Meanwhile I think I got it.
```
Let's examine just the first step in this sequence:

```
```writeln(foo.byPair);
```
```

```
[Tuple!(string, "key", int, "value")("BZP", 5), Tuple!(string, "key", int, "value")("VXE", 8), Tuple!(string, "key", int, "value")("JLC", 2)]
```
```
Well, this look like an array of tuples, each tuple containing a key and a value. I assume, that you understand tuples, I think, they are not the problem here. The problem arises, because the result of "foo.byPair" isn't an array. Actually writeln converts the result to an array, before printing it (or at least it pretends to do so). You can see this with:
```
```
```writeln(typeof(foo.byPair).stringof);
```
```
Which is:

```
```MapResult!(__lambda2, Result)
```
```
```
Ooops, what's that? Having a look at the documentation isn't very instructive (at least at beginners level):
```
```
```auto byPair(AA)(AA aa)
if (isAssociativeArray!AA);
```
```
```
That's almost all you get. Almost, because the description mentions, that the return value is a forward range. Ah, it's a range. I'm not sure, how much you know about ranges. If you want to understand that stuff, you should study them. E.g. try to write some ranges of your own.
```
```
When thinking of a range, I imagine it as sort of a voucher for something like an array. You can use that voucher to get elements from that array. In case of an forward range, you are restricted to get the elements ony by one from the beginning. You get them by using the function front(), which all ranges provide. Let's try it:
```
```
```auto something = foo.byPair;
writeln(something.front);
```
```
And we get:

```
```Tuple!(string, "key", int, "value")("BZP", 5)
```
```
```
That's indeed the first of our elements. We don't know yet, what this range is doing behind the sceens. But I can tell you: When calling byPair it hasn't done much: It just signed that voucher and handed it out to you (that's called lazy evaluation, contrary to eager evaluation). Maybe you never use that voucher. In that case it would be wasted time to calculate all the elements, that are never used.
```
```
The moment you call front, that range starts to do some of the work. It assembles the first item of the range and hand's this out to you. Then it stops again - the other items are not yet calculated. That's done, when you call front again (but before you need to call popFront, to remove the first item, else you would get the item, you allready have, once again). And so on.
```
```
Now we know, how to use this range and that's what "array" does: It calls front and popFront as long as there are more elements (this can be checked by calling empty on the range), and puts them into an array. But what we don't understand yet is that strange type of the range: MapResult!(__lambda2, Result).
```
```
For that, we should have a look at the implementation (I'm using http://dpldocs.info/experimental-docs/std.array.byPair.html for that, because it has a link to the documentation at the bottom), we find out, that byPair is implemented using byKeyValue and map:
```
```
```return aa.byKeyValue
```
.map!(pair => tuple!("key", "value")(pair.key, pair.value));
```
```
byKeyValue is defined in object, which has no source code - I guess it's implemented directly in the compiler somehow. By using typeof, we find out that the type is "Result" and by using writeln we find out, that the result of byKeyValue looks like an array of Pairs of pointers. Again it's a range, that we can use like above.
```
```
This range (think again of a voucher) is now send to map. Map needs, beside this range, a function. You could write that function like:
```
```
```auto make_tuple(Pair pair)
{
return tuple!("key", "value")(pair.key, pair.value);
}
```
```
Than the above could be written as

```
```return aa.byKeyValue.map!(make_tuple);
```
```
```
Beside the fact, that I cannot find the definition of Pair (and therefore would need to make a template instead of the function), it's not necessary to write that function explicitly. There is a way, to write functions more compressed, namely by using =>, like it's done above. Those functions are called lambda-functions (because at some places a greek lambda symbol was used for the function parameter).
```
```
Now, map is lazy too. It just remembers that function, the "voucher" it got and hand's you an other voucher. That's all. This new voucher is called "MapResult", which is actually a struct with functions "front", "popFront" and "empty" (and some more, but we don't care). And this struct has two template-parameters, namely a function and a range. We know that range already, it's Result from byKeyValue. And that function, which has no name, got the name "__lambda2" from the compiler. The 2 suggests, that there is an other lambda somewhere around, but I don't know where. Maybe somewhere inside byKeyValue.
```
```
When now calling front on this MapResult, map starts it's work by calling front on Result. And than it uses whatever it got (a Pair with two points, pointing at "VXE" and 8), to call the lambda-function and hands you back the result of that function (which is a tuple with key "VXE" and value 8).
```

```
If you now go through that whole chain once more, you can understand what happens: byPair takes foo and hands a voucher to array, which hands a voucher to sort, which hands a voucher to map which hands that voucher to writeln. writeln now uses the voucher by asking for the first element. Map calculates it's first element by asking sort. Sort cannot sort, when not knowing all elements (I think). Hence it askes for all the elements and array is busy asking byPair for all the elements and byPair get's them from foo. Now sort sorts and hand's the first element back to map, which transforms it and sends it's result to writeln, which prints.
```
```
When writeln continues and asks for the next element, things work a little bit different. It still asks map and map asks sort. But sort has allready done the whole work and now just sends back the next item. And so on.
```
Hope this helps.
```