CODEWITHSUNDEEP
sortinghaskellgrouping
hellomatey27
hellomatey27

Reputation: 115

Sorting a list of tuples into groups

I have defined a type:

type Sortable = [(String, Integer)]

I would would to sort these into groups based on the string. Right now, I have:

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)

It seems to me that this should work, but it doesn't. :-/

I just get:

• 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)

Upvotes: 1

Views: 127

Answers (1)

Will Ness
Will Ness

Reputation: 71065

You just switched the order of arguments to (:):

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)

And it works with [] as the initial key-values store, as you no doubt intended:

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

Building a result list in reverse by consing unto a list is a common idiom in the more imperative, non-lazy functional languages. In Haskell, thanks to laziness, we can build a list in a top-down manner, with "guarded" recursion:

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

so that there's no need for the extra argument and the result comes in the right order:

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

A more performant way to code this though, is to go via the Data.Map.Map String [Int] route. Leaving it for your researching pleasure.

cf. FromList and friends.

Upvotes: 4

Related Questions