Recursively sort non-contiguous list to list of contiguous lists

Question

I've been trying to learn a bit of functional programming (with Haskell & Erlang) lately and I'm always amazed at the succinct solutions people can come up with when they can think recursively and know the tools.

I want a function to convert a list of sorted, unique, non-contiguous integers into a list of contiguous lists, i.e:

[1,2,3,6,7,8,10,11]

to:

[[1,2,3], [6,7,8], [10,11]

This was the best I could come up with in Haskell (two functions)::

make_ranges :: [[Int]] -> [Int] -> [[Int]]
make_ranges ranges [] = ranges
make_ranges [] (x:xs)
    | null xs = [[x]]
    | otherwise = make_ranges [[x]] xs
make_ranges ranges (x:xs)
    | (last (last ranges)) + 1 == x =
        make_ranges ((init ranges) ++ [(last ranges ++ [x])]) xs
    | otherwise = make_ranges (ranges ++ [[x]]) xs

rangify :: [Int] -> [[Int]]
rangify lst = make_ranges [] lst    

It might be a bit subjective but I'd be interested to see a better, more elegant, solution to this in either Erlang or Haskell (other functional languages too but I might not understand it.) Otherwise, points for just fixing my crappy beginner's Haskell style!

Answer 1

Most straightforward way in my mind is a foldr:

ranges = foldr step []
    where step x [] = [[x]]
          step x acc@((y:ys):zs) | y == x + 1 = (x:y:ys):zs
                                 | otherwise  = [x]:acc

Or, more concisely:

ranges = foldr step []
    where step x ((y:ys):zs) | y == x + 1 = (x:y:ys):zs
          step x acc = [x]:acc

But wait, there's more!

abstractRanges f = foldr step []
    where step x ((y:ys):zs) | f x y = (x:y:ys):zs
          step x acc = [x]:acc

ranges = abstractRanges (\x y -> y == x + 1)
powerRanges = abstractRanges (\x y -> y == x*x) -- mighty morphin

By turning the guard function into a parameter, you can group more interesting things than just +1 sequences.

*Main> powerRanges [1,1,1,2,4,16,3,9,81,5,25]
[[1,1,1],[2,4,16],[3,9,81],[5,25]]

The utility of this particular function is questionable...but fun!

Answer 2

I can't believe I got the shortest solution. I know this is no code golf, but I think it is still quite readable:

import GHC.Exts
range xs = map (map fst) $ groupWith snd $ zipWith (\a b -> (a, a-b)) xs [0..]

or pointfree

range = map (map snd) . groupWith fst . zipWith (\a b -> (b-a, b)) [0..]

BTW, groupWith snd can be replaced with groupBy (\a b -> snd a == snd b) if you prefer Data.List over GHC.Exts

[Edit]

BTW: Is there a nicer way to get rid of the lambda (\a b -> (b-a, b)) than (curry $ (,) <$> ((-) <$> snd <*> fst) <*> snd) ?

[Edit 2]

Yeah, I forgot (,) is a functor. So here is the obfuscated version:

range = map (map fst) . groupWith snd . (flip $ zipWith $ curry $ fmap <$> (-).fst <*> id) [0..]

Suggestions are welcome...