Divide the list into sub-lists: the same values are added to one sublist and different values are ad-CodePudding

Divide the list into sub-lists: the same values are added to one sublist and different values are added to another. Its need to be done using foldr through one pass of the list, without using .

For example:

ghci> splitList [1,2,2,4,5,7,7,8,9] 

[[1],[2,2],[4,5],[7,7],[8,9]]

I did something like that:

splitList :: [Int] -> [[Int]]
splitList = getRes . foldr func5 ([],False,0) where
  func5 c ([],_,_) = ([[c]],False,c)
  func5 c (y@(x:xs), b, l) | c == l = ((c:x):xs, False, c)
                           | b = ((c:x):xs, False, c)
                           | otherwise = ([c]:y, True, c)

getRes :: ([[Int]], Bool, Int) -> [[Int]]
getRes (a,_,_) = a

But it does not work as I expected it to...

ghci> splitList [1,2,2,4,5,7,7,8,9]

[[1],[2,2],[4,5],[7,7,8],[9]]

CodePudding user response：

Since you're using foldr,

> splitList [1,2,2,4,5,7,7,8,9]

[[1],[2,2],[4,5],[7,7],[8,9]]

should work from the right like

> splitList [1,2,2,4,5,7,7,8,9]
                              []
                           [[9]]
                         [[8,9]]
                       [[7,8,9]]
                     [[7,7],[8,9]]
                   [[5],[7,7],[8,9]]
                 [[4,5],[7,7],[8,9]]
               [[2,4,5],[7,7],[8,9]]
             [[2,2],[4,5],[7,7],[8,9]]
           [[1],[2,2],[4,5],[7,7],[8,9]]

Now all that's left is to write this down in code.

As is evident from the above we just need to compare the current element with the head of the "accumulator" (except special casing the last two elements of the list which are collected unconditionally), also maintaining the "sameness" flag. So it can be coded as

splitList :: Eq a => [a] -> [[a]]
splitList xs = snd $ foldr g (undefined,[]) xs
  where
  g x (b,[]) = (b,[[x]])
  g x (_,[y]:t) = (x==y,[x,y]:t)
  g x (b,(a:r):t)
     | (x==a)==b  = (b,(x:a:r):t)
     | otherwise  = (not b, if b then [x]:(a:r):t
                                 else [x,a]:r:t)

Testing:

> splitList [1,2,2,4,5,7,7,8,9]
[[1],[2,2],[4,5],[7,7],[8,9]]

> splitList [1,2,2,4,5,7,7,8,9,9]
[[1],[2,2],[4,5],[7,7],[8],[9,9]]

> splitList [1,2,2,4,5,7,8,9,9,9]
[[1],[2,2],[4,5,7,8],[9,9,9]]