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

Henning Thielemann lemming at henning-thielemann.de
Thu Dec 23 19:20:36 CET 2010

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]

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.

More information about the Haskell-Cafe mailing list