CODEWITHSUNDEEP
haskellfunctional-programming
pacman.
pacman.

Reputation: 227

Splitting list into sorted sublists

How can I divide a list [1,2,4,1,5,7,3,4,2,3] into a list of sublists that would be split at the values that break the sequence. For example a list [1,2,4,1,5,7,3,4,2,3] should yield a list of sublists like [[1,2,4],[1,5,7],[3,4],[2,3]].

Any ideas on this or suggestions how to resolve this problem?

Thanks.

Upvotes: 6

Views: 1659

Answers (5)

Landei
Landei

Reputation: 54574

How about

asc [] = [[]]
asc (x:xs) = map reverse $ reverse $ foldl ins [[x]] xs
    where ins ((y:ys):yss) z | z > y = (z:y:ys) : yss
                             | otherwise = [z] : (y:ys) : yss

or 

asc = map reverse.reverse.foldl ins [[]] 
      where ins [[]] z = [[z]]
            ins ((y:ys):yss) z | z > y = (z:y:ys) : yss
                               | otherwise = [z] : (y:ys) : yss

?

Upvotes: 1

Tener
Tener

Reputation: 5279

Well, this isn't as clean as I would like it to be, but here it is. Using package split: http://hackage.haskell.org/package/split

:m+ Data.List.Split
Prelude Data.List.Split> let f ys = let ys' = zip ys (tail ys) in map (map fst) ((split . whenElt) (uncurry (>)) $ ys')

The braces could be very likely cleaned up here.

Upvotes: 2

Jonathan
Jonathan

Reputation: 2203

Like Travis above, my first thought is to zip the list with its own tail: However, it doesn't look like it quite works in this situation. Not only is there not really a split function that does exactly what you want, but there's also the issue that you will lose an element either off the beginning or the end. In lieu of a properly abstracted solution, take a look at this:

splitAscending :: Ord a => [a] -> [[a]]
splitAscending = foldr f [] where
    f x [] = [[x]]
    f x (y:ys) = if x < head y
    -- It's okay to call head here because the list y is
    -- coming from the summary value of the fold, which is [[a]].
    -- While the sum value may be empty itself (above case), it will
    -- never CONTAIN an empty list.  In general be VERY CAREFUL when
    -- calling head.
        then (x:y):ys -- prepend x to the first list in the summary value
        else [x]:y:ys -- prepend the new list [x] to the summary value

A quick and dirty solution, I hope it suits your needs

-- Also, this is my first post on Stack Overflow :)

Upvotes: 9

Fede
Fede

Reputation: 4016

You can do it with 2 functions, one that splits the head while the first item is lower than the second, and another that takes the output of the function that splits the head, and concats the result of a recursive call to itself with the tail of the list.

splitList :: [Int] -> [[Int]]
splitList [] = []
splitList (x:xs) = ys : splitList zs
    where (ys,zs) = splitHead (x:xs)


splitHead :: [Int] -> ([Int], [Int])
splitHead [x] = ([x], [])
splitHead (x:y:xs)
    | x > y = ([x], (y:xs))
    | x <= y = (x:ys, zs)
    where (ys,zs) = splitHead (y:xs)

Upvotes: 2

Travis Brown
Travis Brown

Reputation: 139028

Here's a hint: whenever you need to look at consecutive elements while processing a list, it's a good idea to start by zipping the list against its tail:

Prelude> let f xs = zip xs $ tail xs
Prelude> f [1,2,4,1,5,7,3,4,2,3]
[(1,2),(2,4),(4,1),(1,5),(5,7),(7,3),(3,4),(4,2),(2,3)]

Now you can use something like splitWhen $ uncurry (>) (where splitWhen is from Data.List.Split) to divide the list appropriately.

Upvotes: 4

Related Questions