Haskell: преобразование списка (a, b) пар ключ-значение (с возможно повторяющимися ключами) в список (a, [b]), сгруппированный по ключу

Ответ 1

Один из самых важных моментов при написании функции пытается разделить то, что он должен делать, на отдельные подзадачи (которые в конце концов объединяются в состав композиции). Например, в определении, которое вы придумали, есть три задачи (в порядке приложения, то есть справа налево в определении):

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

Я хотел опубликовать другое решение (которое было точной копией кода Mark, опубликованного между тем;)). Просто чтобы понять, что большую часть времени существуют разные маршруты к одной и той же цели. В его определении у вас есть отдельные задачи:

• сортировать список по клавишам
• группировать результат по клавишам
• превратить его в список желаемого типа

Еще раз, разделение проблем (модульность) является важным принципом. Просто попробуйте применить его к небольшим проблемам, и как только вы приобретете некоторый опыт, вы сможете придумать удивительно простые решения, казалось бы, трудные проблемы.

Ответ 2

Hoogle - это не единственная поисковая система, которая может искать библиотеки Haskell по типам подписей, и это определенно и, к сожалению, охватывает только небольшую часть Hackage. Поиск с Hayoo для сигнатуры типа [(a,b)]->[(a,[b])] привел эти две реализации:

• aggregateAL
• alistCollect

Что касается вашего решения проблемы, так как в вашей функции вы уже поднимаете структуру данных более высокого уровня (Map), нет смысла переходить к более примитивному ассоциативному списку на выходе, потому что:

• Большинство алгоритмов, которые вы можете использовать для использования таких данных, выиграют от ввода Map, потому что это намного эффективнее для работы с хранилищами значений ключа, и если вы когда-либо находите, что вам все еще нужен список, вы можете всегда используйте toList на месте.
• Map подразумевает отсутствие дубликатов ключей на уровне типа, что не менее важно, так как в Haskell вы всегда должны делать максимальные доказательства, используя систему типов. Этот принцип по существу является тем, что делает утверждение "Если оно компилируется, оно работает", наиболее близкое к истине.

Другими словами, это правильное определение вашей функции:

convertKVList :: (Ord a) => [(a, b)] -> Map a [b]
convertKVList ls =
  Map.fromListWith (++) . map (\(x,y) -> (x,[y])) $ ls

Hayooing для этой сигнатуры типа также дает пару уже реализованных результатов.

Что касается приближающейся проблемы, то она классическая: "Разделить и победить!" . У Криса есть некоторые хорошие моменты в его ответе.

Ответ 3

хотя это никоим образом не является каноническим:

import Data.List
import Data.Ord
import Data.Function (on)

convertKVList :: Ord a => [(a,b)] -> [(a,[b])]
convertKVList = map (\x -> (fst $ head x,  map snd x)) . groupBy ((==) `on` fst) . sortBy (comparing fst)

он имеет то преимущество, что не тянет в Data.Map. должны быть асимптотически одинаковыми, не были сопоставлены. Я думаю, вы могли бы очистить первый кусок Control.Arrow(что-то вроде (fst. Head && & map snd)), но это не очевидно более чистое.

Не уверен, как бы вы пришли к нему, кроме как зная его или спрашивая в #haskell, тем не менее.

Ответ 4

Это похоже на понятное решение, и вы можете немного его очистить:

import Data.Map (toList, fromListWith)
import Control.Arrow (second)

convertKVList :: Ord a => [(a, b)] -> [(a, [b])]
convertKVList = toList . fromListWith (++) . map (second (:[]))

Относительно того, как вы можете это сделать самостоятельно: предполагая, что вы начали с Data.Map, вы хотите использовать карту для объединения значений с равными ключами. Документация для Data.Map в Hackage говорит, что a - это тип значений и k для ключей.

Зная это, вы можете найти a -> a -> a, чтобы найти функции, которые могли бы объединить два значения в Map k a, чтобы создать новое значение a. Это сужает API до нескольких функций, таких как insertWith, fromListWith и fromAscListWith.

Аналогично, чтобы преобразовать ваш Map k a в [(k, a)], вы можете выполнить поиск документации для Map k a -> [(k, a)] и найти только несколько функций, таких как assocs, toList, toAscList и toDescList. Обратите внимание, что в вашем случае [(k, a)] создается на [(Int, [Int])].

Одна вещь, которую я нашел полезной в понимании стандартных библиотек Haskell, - это просмотр источника в Hackage. Увидеть, какие функции реализованы с точки зрения других, помогает уменьшить API, и я вижу, какие функции являются основными строительными блоками.

Ответ 5

Я подозреваю, что без погружения в мутацию и монаду ST вы вряд ли улучшаете решение Map.fromListWith (или, по существу, эквивалентные альтернативы, такие как использование HashMap.fromListWith). Я бы просто пошел с этим.

В принципе, с мутацией вы можете сделать эту группировку в почти линейном времени, используя переменную хеш-таблицу с a в качестве ключей и изменяемых списков b в качестве значений. Однако без мутации это будет хуже, потому что каждая вставка в сбалансированное дерево поиска - O (log n); это связано с тем, что "вставка" означает создание новой копии каждого дерева node, которая ведет к тому, в который входит ваш вставленный элемент. И вам нужно сделать n вставок, что дает вам точно границы O (n * log n), которые функция Map.fromListWith имеет. Сортировка списка ассоциаций заблаговременно не улучшает это, потому что сортировка также O (n * log n).

Итак, чтобы улучшить O (n * log n), вам нужны структуры данных с мутацией. Я просто сделал быстрый Google, и лучше всего было бы реализовать стандартный императивный алгоритм, используя что-то вроде библиотеки hashtables (которая у меня есть никогда не пробовал, поэтому я не могу ручаться за это). Чтобы использовать это, вам нужно будет понять Control.Monad.ST и Data.STRef. Монада ST - это метод, который GHC обеспечивает для использования мутации "внутренне" в чистой функции - он использует некоторые расширения системы типов, чтобы гарантировать, что побочные эффекты не могут наблюдаться вне соответствующих функций. В HaskellWiki есть несколько примеров, но может потребоваться некоторое изучение и практика, чтобы чувствовать себя комфортно с этим.

Другая вещь, которую я бы рекомендовал, если вы хотите, чтобы вы лучше поняли Data.Map или аналогичные библиотеки, стоит взглянуть на книгу Chis Okasaki Purely Functional Data Structures (или его диссертацию (PDF), согласно которой книга основана на). Он основан на стандарте ML вместо Haskell, структуры данных не совпадают, и это может быть немного трудным для чтения, но это основополагающая книга.

Ответ 6

Итак, мое решение переопределяет соответствие шаблонов, потому что я действительно не знаю, какие функции находятся в стандартной библиотеке.

Идея заключалась в том, что если список сортируется по ключам, то вы можете собирать свои ключевые значения по мере продвижения. Чтобы выполнить логику проверки того, добавлять ли к первому списку ключевых значений или создавать новую запись, я использовал шаблоны и стражи для определения условных обозначений. И либеральное использование минусов для добавления значений в список.

И если исходный список не отсортирован, там sortBy.

import Data.List
import Data.Ord

ls = [(2, 1), (1, 2), (1, 4), (1, 3), (2, 3)]

addval [] (k, v)= [(k, [v])]
addval ((k1, vals) : xs) (k2, v) | k1 == k2
  = ((k1, (v : vals)) : xs)
addval ls (k, v) = ((k, [v]) : ls)

convert ls = foldl addval [] (sortBy (comparing fst) ls)

Уродливый код, но он избегает использования Карты.