http://stackoverflow.com/q/14403293

This problem is a natural fit for a [paramorphism](http://stackoverflow.com/a/13317563/849891)
-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 write

    partition_asc xs = para g [] xs  where
      g x (y:_) rs | x<y = (x:a):b where (a:b)=rs
      g x _ rs = [x]:rs

Trivial, since the abstraction fits.

BTW, they have _both_ kinds in Common Lisp - `mapcar` 
(like Haskell's `map`, receiving elements of an input list one by one) 
and `maplist` (receiving "tails" of a list). 
See http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm .

http://stackoverflow.com/q/14403293

This problem is a natural fit for a [paramorphism](http://stackoverflow.com/a/13317563/849891)
-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 write

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

Trivial, since the abstraction fits.

BTW, they have _both_ kinds in Common Lisp - `mapcar` 
(like Haskell's `map`, receiving elements of an input list one by one) 
and `maplist` (receiving "tails" of a list). 
See http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm .

With that idea we get just a slightly less natural encoding,

    import Data.List (tails)

    partition_asc2 xs = foldr g [] (tails xs)  where
      g (x:y:_) ~(a:b) | x<y = (x:a):b
      g (x:_) rs = [x]:rs
      g [] _ = []

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

http://stackoverflow.com/q/14403293

This problem is a natural fit for a [paramorphism](http://stackoverflow.com/a/13317563/849891)
-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 write

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

Trivial, since the abstraction fits.

BTW they have two kinds of `map` in Common Lisp - `mapcar` 
(like Haskell's `map`, processing elements of an input list one by one) 
and `maplist` [(processing "tails" of a list)](http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm).

With that idea we get

    import Data.List (tails)

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

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