Сортировка списка кортежей по группам

Question

Я определил тип:

type Sortable = [(String, Integer)]

Я бы отсортировал их по группам на основе строки.Прямо сейчас у меня есть:

funsort :: Sortable -> [Sortable] -> [Sortable]
funsort [] ret = ret
funsort ((name, value):xs) ret =
  let unsorted = (filter ((/=name).fst) xs) in
  let filtered = (filter ((==name).fst) xs) in
  let listofsortedlists = ((name,value) : homies) in
  funsort unsorted (ret : listofsortedlists)

Мне кажется, что это должно работать, но это не так.: - /

Я просто получаю:

• Couldn't match type ‘(String, Value)’ with ‘[Sortable]’
  Expected type: [[Sortable]]
    Actual type: [(String, Value)]
• In the second argument of ‘(:)’, namely ‘sortedlistoflists’
  In the second argument of ‘funsort’, namely ‘(ret : sortedlistoflists)’
  In the expression: funsort unsorted (ret : sortedlistoflists)

Answer 1

Вы только что изменили порядок аргументов на (:):

funsort :: Sortable -> [Sortable] -> [Sortable]
funsort [] ret = ret
funsort ((name, value):xs) ret =
  let unsorted = (filter ((/=name).fst) xs) in
  let filtered = (filter ((==name).fst) xs) in
  let listofsortedlists = ((name,value) : filtered) in
  funsort unsorted -- (ret : listofsortedlists)   -- wrong order
                   (listofsortedlists : ret)

И он работает с [] как хранилище начальных значений ключа, как вы, без сомнения, и предполагали:

> funsort [("1",1), ("2",10), ("1",100)] []
[[("2",10)],[("1",1),("1",100)]]
it :: [Sortable]

Построение списка результатов в обратном порядке путем преобразования в список - распространенная идиома в более императивных, не ленивых функциональных языках. В Haskell, благодаря лени, мы можем построить список сверху вниз с помощью «guard» рекурсии:

funsort [] = []
funsort ((name, value):xs) =
  let unsorted = (filter ((/=name).fst) xs) in
  let filtered = (filter ((==name).fst) xs) in
  let listofsortedlists = ((name,value) : filtered) in
  listofsortedlists : funsort unsorted 

так что нет необходимости в дополнительном аргументе, и результат приходит в правильном порядке:

> funsort [("1",1), ("2",10), ("1",100)]
[[("1",1),("1",100)],[("2",10)]]

Более эффективный способ кодирования это, хотя бы, идти по маршруту Data.Map.Map String [Int]. Оставьте это для вашего удовольствия.

ср. FromList и друзья.