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

Henning Thielemann lemming at henning-thielemann.de
Thu Dec 23 23:01:18 CET 2010

On Thu, 23 Dec 2010, Stephen Tetley wrote:

> 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
> 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.

More information about the Haskell-Cafe mailing list