Как группировать похожие элементы в списке с помощью Haskell?

Учитывая список кортежей:

dic = [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")] 

Как группировать элементы dic, приводящие к списку grp, где,

 grp = [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])] 

Я на самом деле новичок в Haskell … и, кажется, влюбился в это.
Использование группы или groupBy в Data.List будет группировать только похожие смежные элементы в списке. Я написал для этого неэффективную функцию, но это приводит к сбоям памяти, поскольку мне нужно обработать очень большой кодированный список строк. Надеюсь, вы поможете мне найти более эффективный способ.

Вот мое решение:

 import Data.Function (on) import Data.List (sortBy, groupBy) import Data.Ord (comparing) myGroup :: (Eq a, Ord a) => [(a, b)] -> [(a, [b])] myGroup = map (\l -> (fst . head $ l, map snd l)) . groupBy ((==) `on` fst) . sortBy (comparing fst) 

Это работает, сначала сортируя список с sortBy :

 [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")] => [(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")] 

затем группировка элементов списка с помощью связанного ключа с помощью groupBy :

 [(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")] => [[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]] 

а затем преобразование сгруппированных элементов в кортежи с map :

 [[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]] => [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]`) 

Тестирование:

 > myGroup dic [(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])] 

По возможности повторите использование кода библиотеки.

 import Data.Map sortAndGroup assocs = fromListWith (++) [(k, [v]) | (k, v) <- assocs] 

Попробуйте в ghci:

 *Main> sortAndGroup [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")] fromList [(1,["bb","cc","aa"]),(2,["aa"]),(3,["gg","ff"])] 

Также вы можете использовать расширение TransformListComp , например:

 Prelude> :set -XTransformListComp Prelude> import GHC.Exts (groupWith, the) Prelude GHC.Exts> let dic = [ (1, "aa"), (1, "bb"), (1, "cc") , (2, "aa"), (3, "ff"), (3, "gg")] Prelude GHC.Exts> [(the key, value) | (key, value) <- dic, then group by key using groupWith] [(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])] 
  1. Если список не отсортирован по первому элементу, я не думаю, что вы можете сделать лучше, чем O (nlog (n)).

    • Один простой способ – просто sort а затем использовать что-либо из ответа второй части.

    • Вы можете использовать из Data.Map карту, такую ​​как Map k [a] чтобы использовать первый элемент кортежа в качестве ключа и продолжать добавлять значения.

    • Вы можете написать свою сложную функцию, которая даже после всех попыток все равно будет выполнять O (nlog (n)).

  2. Если список отсортирован по первому элементу, как это имеет место в вашем примере, тогда задача тривиальна для чего-то типа groupBy, как указано в ответе @Mikhail или используется foldr, и существует множество других способов.

Пример использования foldr приведен здесь:

  grp :: Eq a => [(a,b)] -> [(a,[b])] grp = foldr f [] where f (z,s) [] = [(z,[s])] f (z,s) [email protected]((x,y):xs) | x == z = (x,s:y):xs | otherwise = (z,[s]):a 
 {-# LANGUAGE TransformListComp #-} import GHC.Exts import Data.List import Data.Function (on) process :: [(Integer, String)] -> [(Integer, [String])] process list = [(the a, b) | let info = [ (x, y) | (x, y) <- list, then sortWith by y ], (a, b) <- info, then group by a using groupWith] 
  • Сравнение функций в Haskell
  • Что такое «n + k patterns» и почему они запрещены в Haskell 2010?
  • Почему ленивая оценка полезна?
  • Состав функции Haskell (.) И функциональное приложение ($) идиомы: правильное использование
  • Что такое монада?
  • Что делает оператор infix в Haskell?
  • Обработка исключений в Haskell
  • Почему я не должен смешивать вкладки и пробелы?
  • Что представляет собой складку для других типов, кроме списка?
  • Начало работы с Haskell
  • Определение функции уравнениями с различным числом аргументов
  • Давайте будем гением компьютера.