Given list, break it into lists of identical items next to each other:
[1,1,2,4,5,5] ⟼ [[1,1], [2], [4], [5,5]].

And i need to do that using recursion and without higher order functions.

Here what i've got so far

breakList :: [Int] -> [[Int]]
breakList [] = [[]]
breakList [x] = [[x]]
breakList (x:y:rest)
    | x == y = [x] : breakList (y:rest)
    | otherwise = [x] : breakList rest

but it does not work.

CodePudding user response：

You can check if the first item of the result of the recursive call has the same value. If that is the case, we prepend that list with x, otherwise we start a "new group" with x as only member of a list, so [x]:

breakList :: Eq a => [a] -> [[a]]
breakList [] = []
breakList [x] = [[x]]  -- (1)
breakList (x:xs)  -- (2)
  | x == y = (x:ys) : yss  -- (3)
  | otherwise = [x] : ys : yss  -- (4)
  where ~(ys@(y:_):yss) = breakList xs  -- (4)

here we thus first calculate the result of the tail recursion, we know that this will be non-empty since the (x:xs) pattern in (2) will only fire if the list contains at least two items (if it contains only one item, then the (1) clause will fire.

We then can pattern match the result with the pattern ~(ys@(y:_):yss) where ys is the first sublist of the result, y is the first item of that sublist, and yss is a, possibly empty, list of other groups that have been constructed.

We thus can check if the item x we have to put in a group has the same value as the first item y of the first subgroup. If that is the case we use (x:ys) : yss to construct a new lsit where we prepend the first sublist with x (2); if that is not the case, we prepend the sublists with a list [x] to create a new group.

CodePudding user response：

Here is an alternative solution which uses a list as auxiliary data structure during the traversal of the list.

This auxiliary data structure stores the equal element up to now. For each new element (1) we check if it is equal to one of the elements in the auxiliary list, if it is we add it to that list, otherwise (2) we output the auxiliary list as a result and start a new auxiliary list with this new element. At the end (3) we simply output the auxiliary list we have got up to now as the final result.

breakList :: [Int] -> [[Int]]
breakList [] = []
breakList (x:xs) = go [x] xs where
  go ys [] = [ys]                -- (3)
  go ~ys@(y:_) (x:xs)
    | x == y    = go (x:ys) xs   -- (1)
    | otherwise = ys : go [x] xs -- (2)

If you want it to be stable, i.e. all elements must stay in the same order (in the case of integers this does not matter, but it could for other data types), then you have to reverse the output lists:

breakList :: [Int] -> [[Int]]
breakList [] = []
breakList (x:xs) = go [x] xs where
  go ys [] = [reverse ys]
  go ~ys@(y:_) (x:xs)
    | x == y    = go (x:ys) xs
    | otherwise = reverse ys : go [x] xs

This algorithm also assumes that == is transitive, which is not technically necessary, but certainly the case for integers. Although, the specification you've given is ambiguous if == is not transitive, which element should we compare each new element to? The first element of the group, or the previous element? Anyway, it is probably not something you have to worry about.