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

On Thu, 23 Dec 2010, Stephen Tetley wrote:

On 23 December 2010 21:12, Stephen Tetley wrote:

...

I'd go with direct recursion for this one - the pattern of consumption and production that generates the answer doesn't seem to neatly match any of the standard recursion combinators (map, unfold, fold, mapAccum, ...) nor exotic ones (skipping streams c.f. the Stream fusion paper, apomorphisms, ...).

Here's a synthesized functional that matches the needed behaviour.

It takes from:

a) apomorphism - has a final flush operation b) skipping streams (the Stream fusion paper) - a skipping Next case, though in this case there is no Done c) unfoldMap - itself a synthetic combination of unfold and map, which is unfolding against a list as well as state (the unfold equivalent of mapAccumL).

Unimaginatively I've called it "lessproductive" as it can produce less than it consumes, though as it has no Done it must consume everything...

data Step st a = Yield a !st | Next !st

This could be seen as "type Step st a = (Maybe a, st)". I have thought about mapping from [Int] to [Maybe (Int, Int)] by mapAccumL, then compressing the result with catMaybes. However we need to append a final pair when the end of the list is reached, which risks a memory leak.

This one looks somewhat symmetrical: f xs = let xys = filter ( \ (x,y) -> y - x > 1 ) $ zip xs ( tail xs ) in zip ( [ head xs ] ++ map snd xys ) ( map fst xys ++ [ last xs ] )