Bug 5502 – More handy ways to create associative arrays

I think some helpers to create built-in associative arrays will be useful. Such helpers may be built-in methods of the AAs, or free functions in std.algorithm, or a mix of the two. Three of the most common ways to build an associative array (examples in Python 2.6.6): 1) One of the most useful ways to create an AA is from a sequence of pairs. The pairs may come from zipping of two iterables: >>> a [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> b = range(10, 100, 10) >>> b [10, 20, 30, 40, 50, 60, 70, 80, 90] >>> zip(a, b) [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60), (7, 70), (8, 80), (9, 90)] >>> dict(zip(a, b)) {1: 10, 2: 20, 3: 30, 4: 40, 5: 50, 6: 60, 7: 70, 8: 80, 9: 90} Or from sorting and then grouping: >>> from itertools import groupby >>> s = "abaacaabbabaa" >>> t = "".join(sorted(s)) >>> t 'aaaaaaaabbbbc' >>> [(h, len(list(g))) for h,g in groupby(t)] [('a', 8), ('b', 4), ('c', 1)] >>> dict((h, len(list(g))) for h,g in groupby(t)) {'a': 8, 'c': 1, 'b': 4} In Phobos of DMD 2.051 there are a zip() and group() that return such iterables of pairs. So the only needed thing is a free function to build an AA from such sequences, or better a built-in AA method like AA.fromPairs(). See also the Scala xs.toMap method: http://www.scala-lang.org/api/current/scala/collection/immutable/List.html See also AA.byPair() from bug 5466. AA.fromPairs(AA.byPair()) is an identity. ---------------------- 2) Often you need to create an associative array that represents key-frequency pair, but you want to avoid to waste time sorting the items and then grouping them: >>> from random import randint >>> from collections import defaultdict >>> d = defaultdict(int) >>> s = "abaacaabbabaa" >>> for c in s: d[c] += 1 ... >>> d defaultdict(<type 'int'>, {'a': 8, 'c': 1, 'b': 4}) This is equivalent to a way to create a bag data structure. For this purpose I don't suggest to add a built-in method to AAs. A free frequency() function for std.algorithm will be enough. ---------------------- 3) A simple and common way to create an associative array is from an iterable of keys, with constant values: >>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> dict.fromkeys(a) {1: None, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None} >>> dict.fromkeys(a, 1) {1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1} This may become a built-in AA method like AA.fromKeys(), or a similar free function in std.algorithm (in a statically typed language as D the type of the values must be somehow given or be known, even when fromKeys() is allowed to use a default value).

The first suggestion was implemented: https://github.com/D-Programming-Language/phobos/compare/467db2b45d92...c850e68b0379 This works: import std.stdio, std.array, std.algorithm; void main() { dchar[] s = "abaacaabbabaa"d.dup; s.sort(); uint[dchar] aa = ['a':8, 'b':4, 'c':1]; assert(group(s).assocArray() == aa); }

Currently if you want to create an associative array with constant values you have to use something like: import std.array: assocArray; import std.range: zip, repeat; void main() { bool[dchar] dcharSet = assocArray(zip("ABCD", repeat(true))); } In Python the dict has a static method "fromkeys" that is handy: >>> dict.fromkeys("ABCD", True) {'A': True, 'C': True, 'B': True, 'D': True} A possible similar Phobos function: import std.array: AAFromKeys; void main() { bool[dchar] dcharSet = AAFromKeys("ABCD", true); }

Regarding the second suggestion, now I prefer a more general solution. One possible name for this free function that returns an associative array is "gather", as maybe in Perl6. As use case this program shows some of the anagrams, given a file of different lowercase words: import std.stdio, std.algorithm, std.range, std.string, std.file; void main() { string[][const ubyte[]] anags; foreach (string w; std.array.splitter("unixdict.txt".readText)) anags[w.dup.representation.sort().release.idup] ~= w; writefln("%-(%s\n%)", anags .byValue .filter!q{ a.length > 2 } .take(20)); } A gather() higher order function allows to remove the foreach and replace it with: const anags = std.array.splitter("unixdict.txt".readText) .gather(w => w.dup.representation.sort().release.idup); gather() takes a callable that specifies how to compute the key of the associative array.

(In reply to comment #3) > One possible name for this free function that returns an associative array is > "gather", as maybe in Perl6. I was wrong, in Perl6 it's named "classify" (List.classify): http://doc.perl6.org/routine/classify multi sub classify(&mapper, *@values) returns Hash:D multi method classify(List:D: &mapper) returns Hash:D Transforms a list of values into a hash representing the classification of those values according to a mapper; each hash key represents the classification for one or more of the incoming list values, and the corresponding hash value contains an array of those list values classified by the mapper into the category of the associated key. Examples: say classify { $_ %% 2 ?? 'even' !! 'odd' }, (1, 7, 6, 3, 2); # ("odd" => [1, 7, 3], "even" => [6, 2]).hash;; say ('hello', 1, 22/7, 42, 'world').classify: { .Str.chars } # ("5" => ["hello", "world"], "1" => [1], "8" => [22/7], "2" => [42]).hash

> import std.array: AAFromKeys; > void main() { > bool[dchar] dcharSet = AAFromKeys("ABCD", true); > } This is already easily possible today: --- assocArray("ABCD".zip(true.repeat)).writeln; --- https://run.dlang.io/is/7j1ObE We could add another overload to assocArray that accepts two arguments: values + keys -> PR: https://github.com/dlang/phobos/pull/6155

Commits pushed to master at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/3cfe2c11fa979560f354f847a6f2708584fd8966 Fix Issue 5502 - More handy ways to create associative arrays https://github.com/dlang/phobos/commit/f961aa86863938c964baea345684309b85021000 Merge pull request #6155 from wilzbach/fix-5502 Fix Issue 5502 - More handy ways to create associative arrays merged-on-behalf-of: Nathan Sashihara <[email protected]>