[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]
[(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.
More information about the Haskell-Cafe
mailing list