import Test.QuickCheck
import Data.List (sort)

ups :: Ord a => [a] -> [[a]]
ups xs = ups2 xs []

ups2 :: Ord a => [a] -> [a] -> [[a]]
ups2 (x:xs) (y:ys)
  | x >= y      =  ups2 xs (x:y:ys)
  | otherwise   =  reverse (y:ys) : ups2 (x:xs) []
ups2 (x:xs) []  =  ups2 xs [x]
ups2 []     ys  =  [reverse ys]

prop_ups_same :: [Int] -> Bool
prop_ups_same xs = concat(ups xs) == xs

prop_ups_asc :: [Int] -> Bool
prop_ups_asc xs =
  and [asc us | us <- ups xs]

prop_ups_not_null :: [Int] -> Bool
prop_ups_not_null xs =
  and [not(null us) | us <- ups xs]

prop_ups_max :: [Int] -> Bool
prop_ups_max xs =
  and [ last us1 > head us2 | (us1,us2) <- zip uss (tail uss) ]
  where uss = ups xs

asc xs  =  sort xs == xs