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

Stephen Tetley stephen.tetley at gmail.com
Thu Dec 23 22:52:29 CET 2010

On 23 December 2010 21:12, Stephen Tetley <stephen.tetley at gmail.com> 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

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

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

lessproductive :: (st -> a -> Step st b) -> (st -> b) -> st -> [a] -> [b]
lessproductive phi flush = step
    step st []     = [flush st]
    step st (x:xs) = case phi st x of
                       Next st' -> step st' xs
                       Yield b st' -> b : step st' xs

ranges :: (Num a, Eq a) => [a] -> [(a,a)]
ranges []     = []
ranges (x:xs) = lessproductive phi id (x,x) xs
    phi (i,j) n | j+1 == n = Next (i,n)
    phi ans   n            = Yield ans (n,n)

More information about the Haskell-Cafe mailing list