[Haskell-cafe] List of numbers to list of ranges

[Henning Thielemann]

On Thu, 23 Dec 2010, C K Kashyap wrote:

> Here's my attempt to convert a list of integers to a list of range tuples -
>
> Given [1,2,3,6,8,9,10], I need [(1,3),(6,6),8,10)]

That's an interesting problem!

My first attempt:

> List.unfoldr (\xs -> case xs of [] -> Nothing; y:ys -> case span (uncurry (==)) $ zip xs [y..] of (matching, remainder) -> Just ((y, fst $ last matching), map fst remainder)) [1,2,3,6,8,9,10]
[(1,3),(6,6),(8,10)]


However, the use of 'last' will course a memory leak for long ranges, and 
the (map fst remainder) reconstructs the remainder of the list, and thus 
needs linear time instead of constant one.

Here is my second attempt, developed in GHCi and variable names that 
should be improved ...

List.unfoldr (\xs -> case xs of [] -> Nothing; y:ys -> case dropWhile (\(a,b,t) -> case t of [] -> False; h:_ -> a==h) $ zip3 [y+1..] xs (List.tails ys) of ~((_, end, remainder):_) -> Just ((y, end), remainder)) [1,2,3,6,8,9,10]

Using zip3 I have bundled all information that I need after 'dropWhile' in 
order to proceed: The end of the current range and the remaining numbers.