1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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 . |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | 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). |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 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). |