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)]