Convert a list of things into a list of sublists

Question

I want to write a function that converts a list of things into a list of sublists, each containing elements of the same value, which when concatenated together give the same list.

So runs [1,2,2,1,3,3,3,2,2,1,1,4] becomes [[1],[2,2],[1],[3,3,3],[2,2],[1,1],[4]]

How do I solve this problem in Haskell?

Answer 1

This function already exists, this is group :: Eq a => [a] -> [[a]]:

Prelude> import Data.List(group)
Prelude Data.List> group [1,2,2,1,3,3,3,2,2,1,1,4]
[[1],[2,2],[1],[3,3,3],[2,2],[1,1],[4]]

Answer 2

It is often fruitful to check Hoogle when you're looking for a function that might already exist. Because you can search by type, you don't have to know what the function is called. And even if it doesn't exist, it's a good exercise because it makes you think about what type it should have.

Here, the simple type to start with is [a] -> [[a]], but this search yields no results. On reflection this makes sense: you can't split a list of arbitrary objects without some way to compare them.

There are a few ways you might think of to compare list items. One obvious one, since you want to group items that are equal, is Eq. So you might try a search for Eq a => [a] -> [[a]], and this in fact yields group. You might similarly try Ord a instead, since Ord is another way to compare things, but this yields no results.

Lastly you might try the most general thing possible: take in a predicate function dictating where to split the list. A search for (a -> a -> Bool) -> [a] -> [[a]] yields groupBy, which is another reasonable way of achieving your goal, though in fact more general than necessary.