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

[Daniel Fischer]

On Thursday 23 December 2010 18:27:43, C K Kashyap wrote:
> Hi all,
>
> 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)]
>
> My attempt using foldl yields me the output in reverse. I can ofcourse
> reverse the result, but what would be a better way?
>
> f xs = foldl ff [] xs
> 	where
> 	  	[]  `ff` i = [(i,i)]
> 		((s,e):ns) `ff` i = if i == e+1 then
> 					(s,i):ns
> 					else
> 					(i,i):(s,e):ns
>
> Regards,
> Kashyap

I suggested:

> Prelude> let foo k [] = [(k,k)]; foo k xs@((l,h):t) = if l == k+1 then
> (k,h):t else (k,k):xs
> Prelude> foldr foo [] [1,2,3,6,8,9,10]
> [(1,3),(6,6),(8,10)]

Lazier is better:

bar k xs = (k,m):t
  where
    (m,t) = case xs of
              [] -> (k,[])
              (l,h):u | l == k+1 -> (h,u)
                      | otherwise -> (k,xs)

Prelude> foldr foo [] [1 .. 1000000]
[(1,1000000)]
(15.46 secs, 226229904 bytes)
Prelude> foldr bar [] [1 .. 1000000]
[(1,1000000)]
(3.47 secs, 242992364 bytes)