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

[Henning Thielemann]

On Thu, 23 Dec 2010, Daniel Fischer wrote:

> 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
>>
>
> A right fold?
> It's easier, at least:
>
> 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)]

I admit your solution is much more comprehensible than my one. However, my 
second complicated solution should be more efficient and especially works 
as good as possible on infinite lists:

Prelude> List.unfoldr (...) [1..]
[(1,


I try other ones (using Data.List.HT from utility-ht):

Prelude> map (\xs -> (head xs, last xs)) $ Data.List.HT.groupBy (\a b -> a+1==b) [1,2,3,6,8,9,10]
[(1,3),(6,6),(8,10)]
Prelude> map (\xs@(x:_) -> (x, x + length xs - 1)) $ Data.List.HT.groupBy (\a b -> a+1==b) [1,2,3,6,8,9,10]
[(1,3),(6,6),(8,10)]

The second one should not have a memory leak, like the first one.

If you prefer an explicit recursive solution, how about this one:

Prelude> let ranges xs = (case xs of [] -> []; y:ys -> aux0 y ys); aux0 y ys = let (end,remainder) = aux1 y ys in (y,end) : remainder; aux1 predec xs = case xs of [] -> (predec, []); y:ys -> if predec+1 == y then aux1 y ys else (predec, aux0 y ys)
Prelude> ranges [1,2,3,6,8,9,10]
[(1,3),(6,6),(8,10)]