- A+

I have to split the given list into non-empty sub-lists each of which is either in strictly ascending order, in strictly descending order, or contains all equal elements. For example, [5,6,7,2,1,1,1] should become [[5,6,7],[2,1],[1,1]].

Here is what I have done so far:

`splitSort :: Ord a => [a] -> [[a]] splitSort ns = foldr k [] ns where k a [] = [[a]] k a ns'@(y:ys) | a <= head y = (a:y):ys | otherwise = [a]:ns' `

I think I am quite close but when I use it it outputs [[5,6,7],[2],[1,1,1]] instead of [[5,6,7],[2,1],[1,1]].

Here is a kinda ugly solution, with three `reverse`

in one line of code :).

`addElement :: Ord a => a -> [[a]] -> [[a]] addElement a [] = [[a]] addElement a (x:xss) = case x of (x1:x2:xs) | any (check a x1 x2) [(==),(<),(>)] -> (a:x1:x2:xs):xss | otherwise -> [a]:(x:xss) _ -> (a:x):xss where check x1 x2 x3 op = (x1 `op` x2) && (x2 `op` x3) splitSort xs = reverse $ map reverse $ foldr addElement [] (reverse xs) `

You can possibly get rid of all the reversing if you modify `addElement`

a bit.

EDIT: Here is a less reversing version (even works for infinite lists):

`splitSort2 [] = [] splitSort2 [x] = [[x]] splitSort2 (x:y:xys) = (x:y:map snd here):splitSort2 (map snd later) where (here,later) = span ((==c) . uncurry compare) (zip (y:xys) xys) c = compare x y `

EDIT 2: Finally, here is a solution based on a single decorating/undecorating, that avoids comparing any two values more than once and is probably a lot more efficient.

`splitSort xs = go (decorate xs) where decorate :: Ord a => [a] -> [(Ordering,a)] decorate xs = zipWith (/x y -> (compare x y,y)) (undefined:xs) xs go :: [(Ordering,a)] -> [[a]] go ((_,x):(c,y):xys) = let (here, later) = span ((==c) . fst) xys in (x : y : map snd here) : go later go xs = map (return . snd) xs -- Deal with both base cases `