# 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.

**EDIT**: see also
an alternative definition for Data.List.groupBy