Список внутри словаря

[metaclass]

А вот как правильно сделать такую иммутабельную функциональную структуру данных:

есть словарь(map) из строк в качестве ключей и некоей структуры в качестве значений. Причем эта структура содержит внутри себя список. Для простоты можно считать что структура и есть просто список.
И задача - заполнить оный словарь имея список пар "строка-ключ, значение для списка". Ключи в списке пар повторяются. Короче, что-то вроде "select key,list(value) from KeyValuePairs group by key".

Наверно, можно предварительно отсортировать список по ключам, затем просто пройтись по списку, объединяя списки пар с одинаковыми ключами в пару "ключ, список значений" и полученное затем засунуть в словарь.

Comments

[x-a-e-p.livejournal.com]

вставки делать надо(то есть после начального заполнения структуры изменяться она не будет)? если нет, то собственно, отсортированный по ключу массив (ключ, значение) и есть такая структура.

[http://users.livejournal.com/_slw/]

push @{$Dict{$key}}, $value;

[(Anonymous)]

Кажется, в простейшем случае вам подходит Data.Map.insertWith (++).

[gds.livejournal.com]

правильно -- в зависимости от того, что делают с ключами потом, для доступа по ним. В среднем случае -- какое-нибудь avl tree (есть доказанно-корректная реализация, если чо), значения которого хранят эти самые list(value) (либо список, либо finger trees).
А вот как такое строить -- есть разные идеи. Если очень хочется эффективности, можно сделать слияние деревьев, где для слияния значений будет использоваться какая-нибудь из эффективных форм склеивания содержимого (для списков -- зависит от списков и семантики языка, для finger trees -- всё однозначно).

[permea-kra.livejournal.com]

>>есть словарь(map) из строк в качестве ключей
http://hackage.haskell.org/package/list-tries-0.2

>>И задача - заполнить оный словарь имея список пар "строка-ключ, значение для списка"
http://hackage.haskell.org/packages/archive/fingertree/0.0.1.0/doc/html/Data-FingerTree.html В вариации секуэнса (см статью из заголовка)