Split a list into non-empty sub-lists in Haskell

  • 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 


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: