Brandon.Si(mmons)

code / art / projects

An Alternative Definition for Data.List.groupBy

The function groupBy from haskell’s standard library is defined in terms of span, the effect being that the supplied predicate function is used to compare the first element of a group with successive elements.

This isn’t clear from the docs, and you might try to do this and wonder at the output you got:

*Main> groupBy (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5,3],[2],[1,4,4,1,1,2,3,4,5,4,5,6,7]]

We can redefine groupBy as follows, so that the supplied predicate function compares adjacent elements one-by-one and returns True if they should be grouped together:

1
2
3
4
5
6
7
8
9
groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' c [] = []
groupBy' c (a:as) = (a:ys) : groupBy' c zs
    where (ys,zs) = spanC a as
          spanC _ [] = ([], [])
          spanC a' (x:xs)
            | a' `c` x = let (ps,qs) = spanC x xs
                          in (x:ps,qs)
            | otherwise = ([], x:xs)

Now we can use the groupBy function to return a list of ascending lists, like we (probably) wanted:

*Main> groupBy' (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5],[3],[2],[1,4,4],[1,1,2,3,4,5],[4,5,6,7]]

The functionality is of course the same for groupBy (==).

Comments