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],,[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