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

[Stephen Tetley]

On 23 December 2010 22:01, Henning Thielemann
<lemming at henning-thielemann.de> wrote:

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

Hi Henning

Thanks - that's an extra nesting of constructors though.

Note the flush in the original was always doomed to be productive -
this revision might be better, the flush now has the option of
producing nothing or many:


lessproductive :: (st -> a -> Step st b) -> (st -> [b]) -> st -> [a] -> [b]
lessproductive phi flush = step
  where
    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


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