Haskell equivalent to Scala's groupBy

Question

Scala has a function groupBy on lists that accepts a function for extracting keys from list items, and returns another list where the items are tuples consisting of the key and the list of items producing that key. In other words, something like this:

List(1,2,3,4,5,6,7,8,9).groupBy(_ % 2)
// List((0, List(2,4,6,8)), (1, List(1,3,5,7,9)))

(Actually, it looks like in current versions it provides a Map instead, but that's not important). C# has an even more useful version that lets you map the values at the same time (very useful if, say, your key function is just extracting part of a tuple).

Haskell has a groupBy, but it's somewhat different - it groups runs of things according to some comparison function.

Before I go and write it, is there an equivalent of Scala's groupBy in Haskell? Hoogle doesn't have anything for what I'd expect the signature to look like (below), but I may have just got it wrong.

Eq b => (a -> b) -> [a] -> [(b,[a])]

Answer 1

You can write the function yourself rather easily, but you need to place an Ord or Hashable constraint on the result of the classifier function if you want an efficient solution. Example:

import Control.Arrow ((&&&))
import Data.List
import Data.Function

myGroupBy :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
myGroupBy f = map (f . head &&& id)
                   . groupBy ((==) `on` f)
                   . sortBy (compare `on` f)

> myGroupBy (`mod` 2) [1..9]
[(0,[2,4,6,8]),(1,[1,3,5,7,9])]      

You can also use a hash map like Data.HashMap.Strict instead of sorting for expected linear time.

Answer 2

Specifically, the following should work:

scalaGroupBy f = groupBy ((==) `on` f) . sortBy (comparing f)

modulo that this doesn't get you the result of f in each group, but if you really need it you can always post-process with

map (\xs -> (f (head xs), xs)) . scalaGroupBy f

Answer 3

This isn't a function in the List library.

You can write it as the composition of sortBy and groupBy.