The Definition of Data.List.group

I’ve been thinking quite a bit lately about a category of functions that are always a bit awkward to define: they involve cases where we would like to traverse a recursive data structure and do something with the data that we have passed over but which is “gone now”. There are many examples of functions like these in the haskell standard libraries: [span](http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/GHC-List.html#span), [splitAt](http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/GHC-List.html#splitAt), etc.

A function like group is in this category. It’s conceptually very simple, but defining it actually requires a bit of indirection. Here I’ve translated the definition from Data.List to use explicit recursion:

group :: (Eq a) => [a] -> [[a]]
group [] = []
group (a:as) = (a:ys) : group zs
    where (ys,zs) = spanEq as
          spanEq [] = ([], [])
          spanEq (x:xs)
              | a == x = let (ps,qs) = spanEq xs
                          in (x:ps,qs)
              | otherwise = ([], x:xs)

I think if I were asked to define this having never seen it, the first thing I would think of would be something using foldl1, which wouldn’t work.