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

by

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.

More Related Contents:

  1. Haskell finding mean of cubes of odd members Any ideas? [closed]
  2. Histogram in Haskell [closed]
  3. What is Haskell’s Stream Fusion
  4. Using return vs. not using return in the list monad
  5. Cartesian product of infinite lists in Haskell
  6. Decrementing ranges in Haskell
  7. Zip with default value instead of dropping values?
  8. Replace individual list elements in Haskell?
  9. Using Haskell’s map function to calculate the sum of a list
  10. Merging two lists in Haskell
  11. Haskell Monad – How does Monad on list work?
  12. Is there a function to flatten a nested list of elements?
  13. Linked list partition function and reversed results
  14. Understanding a recursively defined list (fibs in terms of zipWith)
  15. Removing duplicates from a list in Haskell without elem
  16. Removing syntactic sugar: List comprehension in Haskell
  17. Counting unique elements in a list
  18. Unsequence Monad function within Haskell
  19. Grouping a list into lists of n elements in Haskell
  20. How to check a list contains substring from other list using scala?
  21. prolog change show answer to print into list
  22. Prolog – count repetitions in list
  23. Combining (cbind) vectors of different length
  24. Find powers of 2 in a list Prolog
  25. Flatten a list in Prolog
  26. How to flatten a list to a list without coercion?
  27. In Dart, what’s the difference between List.from and .of, and between Map.from and .of?
  28. Extract list of attributes from list of objects in python
  29. List.shuffle() in Dart?
  30. Recursive Prolog predicate for reverse / palindrome

Leave a Comment