Need to partition a list into lists based on breaks in ascending order of elements (Haskell)

Say I have any list like this:

[4,5,6,7,1,2,3,4,5,6,1,2]

I need a Haskell function that will transform this list into a list of lists which are composed of the segments of the original list which form a series in ascending order. So the result should look like this:

[[4,5,6,7],[1,2,3,4,5,6],[1,2]]

Any suggestions?

You can do this by resorting to manual recursion, but I like to believe Haskell is a more evolved language. Let's see if we can develop a solution that uses existing recursion strategies. First some preliminaries.

{-# LANGUAGE NoMonomorphismRestriction #-}
-- because who wants to write type signatures, amirite?
import Data.List.Split -- from package split on Hackage

Step one is to observe that we want to split the list based on a criteria that looks at two elements of the list at once. So we'll need a new list with elements representing a "previous" and "next" value. There's a very standard trick for this:

previousAndNext xs = zip xs (drop 1 xs)

However, for our purposes, this won't quite work: this function always outputs a list that's shorter than the input, and we will always want a list of the same length as the input (and in particular we want some output even when the input is a list of length one). So we'll modify the standard trick just a bit with a "null terminator".

pan xs = zip xs (map Just (drop 1 xs) ++ [Nothing])

Now we're going to look through this list for places where the previous element is bigger than the next element (or the next element doesn't exist). Let's write a predicate that does that check.

bigger (x, y) = maybe False (x >) y

Now let's write the function that actually does the split. Our "delimiters" will be values that satisfy bigger; and we never want to throw them away, so let's keep them.

ascendingTuples = split . keepDelimsR $ whenElt bigger

The final step is just to throw together the bit that constructs the tuples, the bit that splits the tuples, and a last bit of munging to throw away the bits of the tuples we don't care about:

ascending = map (map fst) . ascendingTuples . pan

Let's try it out in ghci:

*Main> ascending [4,5,6,7,1,2,3,4,5,6,1,2]
[[4,5,6,7],[1,2,3,4,5,6],[1,2]]
*Main> ascending [7,6..1]
[[7],[6],[5],[4],[3],[2],[1]]
*Main> ascending []
[[]]
*Main> ascending [1]
[[1]]

P.S. In the current release of split, keepDelimsR is slightly stricter than it needs to be, and as a result ascending currently doesn't work with infinite lists. I've submitted a patch that makes it lazier, though.

ascend :: Ord a => [a] -> [[a]]
ascend xs = foldr f [] xs
  where
    f a []  = [[a]]
    f a xs'@(y:ys) | a < head y = (a:y):ys
                   | otherwise = [a]:xs'

In ghci

*Main> ascend [4,5,6,7,1,2,3,4,5,6,1,2]
[[4,5,6,7],[1,2,3,4,5,6],[1,2]]

This problem is a natural fit for a paramorphism-based solution. Having (as defined in that post)

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs)  =  c x xs (para  c n xs)
foldr c n (x : xs)  =  c x    (foldr c n xs)
para  c n []        =  n
foldr c n []        =  n

we can write

partition_asc xs  =  para c [] xs  where
  c x (y:_) ~(a:b) | x<y  =  (x:a):b 
  c x  _      r           =  [x]:r 

Trivial, since the abstraction fits.

BTW they have two kinds of map in Common Lisp - mapcar (processing elements of an input list one by one) and maplist (processing "tails" of a list). With this idea we get

import Data.List (tails)

partition_asc2 xs  =  foldr c [] . init . tails $ xs  where
  c (x:y:_) ~(a:b) | x<y  =  (x:a):b
  c (x:_)     r           =  [x]:r 

Lazy patterns in both versions make it work with infinite input lists in a productive manner (as first shown in Daniel Fischer's answer).

update 2020-05-08: not so trivial after all. Both head . head . partition_asc $ [4] ++ undefined and the same for partition_asc2 fail with *** Exception: Prelude.undefined. The combining function g forces the next element y prematurely. It needs to be more carefully written to be productive right away before ever looking at the next element, as e.g. for the second version,

partition_asc2' xs  =  foldr c [] . init . tails $ xs  where
  c (x:ys) r@(~(a:b))  =  (x:g):gs
         where
         (g,gs) | not (null ys) 
                  && x < head ys =  (a,b)
                | otherwise      =  ([],r)

(again, as first shown in Daniel's answer).

You can use a right fold to break up the list at down-steps:

foldr foo [] xs
  where
    foo x yss = (x:zs) : ws
      where
        (zs, ws) = case yss of
                     (ys@(y:_)) : rest
                            | x < y     -> (ys,rest)
                            | otherwise -> ([],yss)
                     _ -> ([],[])

(It's a bit complicated in order to have the combining function lazy in the second argument, so that it works well for infinite lists too.)