How do I combine consectuive numbers in a list into a range in Haskell?

Question

I'm trying to grapple my head around Haskell and I'm having a hard time pinning down the general procedure/algorithm for this specific task. What I want to do is basically give Haskell a list [1,2,3,5,6,9,16,17,18,19] and have it give me back [1-3, 5, 6, 9, 16-19] so essentially turning three or more consecutive numbers into a range in the style of lowestnumber - highestnumber. What I have issue with it I suppose is the all too common difficulty grappling with with the functional paradigm of Haskell. So I would really appreciate a general algorithm or an insight into how to view this from an "Haskellian" point of view.

Thanks in advance.

Answer 1

If I understand the question correctly, the idea is to break up the input lists in chunks, where a chunk is either a single input element or a range of at least three consecutive elements.

So, let's start by defining a datatype for representing such chunks:

data Chunk a = Single a | Range a a

As you can see, the type is parametric in the type of input elements.

Next, we define a function chunks to actually construct a list of chunks from a list of input elements. For this, we require the ability to compare input elements and to obtain the immediate consecutive for a given input element (that is, its successor). Hence, the type of the function reads

chunks :: (Eq a, Enum a) => [a] -> [Chunk a]

Implementation is relatively straightforward:

chunks = foldr go []
 where
  go x (Single y : Single z : cs) | y == succ x && z == succ y = Range x z : cs
  go x (Range y z : cs) | y == succ x = Range x z : cs
  go x cs                             = Single x : cs

We traverse the list from right to left, generating chunks as we go. We generate a range if an input element precedes its two immediate consecutive elements (the first case of the helper function go) or if it precedes a range that starts with its immediate consecutive (the second case). Otherwise, we generate a single element (the final case).

To arrange for pretty output, we declare applications of the type constructor Chunk to be instances of the class Show (given that the type of input elements is in Show):

instance Show a => Show (Chunk a) where
  show (Single x ) = show x
  show (Range x y) = show x ++ "-" ++ show y

Returning to the example from the question, we then have:

> chunks [1,2,3,5,6,9,16,17,18,19]
[1-3,5,6,9,16-19]

---

Unfortunately, things are slightly more complicated if we need to account for bounded element types; such types have a largest element for which succ is undefined:

> chunks [maxBound, 1, 2, 3] :: [Chunk Int]
*** Exception: Prelude.Enum.succ{Int}: tried to take `succ' of maxBound

This suggests that we should abstract from the specific approach for determining whether one elements succeeds another:

chunksBy :: (a -> a -> Bool) -> [a] -> [Chunk a]
chunksBy succeeds = foldr go []
 where
  go x (Single y : Single z : cs) | y `succeeds` x && z `succeeds` y =
    Range x z : cs
  go x (Range y z : cs) | y `succeeds` x = Range x z : cs
  go x cs = Single x : cs

Now, the version of chunks that was given above, can be expressed in terms of chunksBy simply by writing

chunks :: (Eq a, Enum a) => [a] -> [Chunk a]
chunks = chunksBy (\y x -> y == succ x)

Moreover, we can now also implement a version for bounded input types as well:

chunks' :: (Eq a, Enum a, Bounded a) => [a] -> [Chunk a]
chunks' = chunksBy (\y x -> x /= maxBound && y == succ x)

That merrily gives us:

> chunks' [maxBound, 1, 2, 3] :: [Chunk Int]
[9223372036854775807,1-3]