Merge adjacent numeric intervals

Question

Given a list of pairs of integers that represent closed numeric intervals, I need to output a list of intervals where the adjacent intervals are merged together. The code assumes that the intervals do not overlap and that a <= b in all pairs (a, b).

Intervals (a,b) and (c,d) are adjacent if b + 1 == c.

merge []         = []
merge [x]        = [x]
merge ((a, b):(c, d):xs)
    | b + 1 == c = merge ((a, d):xs)
    | otherwise  = (a, b):(merge ((c, d):xs))

Maybe I can simplify this and use fold or something like that? Also, would converting this to a tail recursive version make sense here?

Answer 1

A fold isn't a great fit for this problem, they don't support any sort of pushback so you'd have to get fancy with the accumulator value and it certainly wouldn't get any prettier.

Tail recursion isn't an important concept in Haskell ([1], [2], &c). If you have a specific performance concern feel free to bring it up, but I don't see any particular reason to think your function is more likely to blow the stack than any other.

I can't come up with any appreciably simpler solutions than yours, but you might like this version which has more reusable components.

redistributeIn :: [(a, b)] -> Maybe (a, [(b, a)], b)
redistributeIn []             = Nothing
redistributeIn xs@((a0, _):_) = (a0, insides xs, b0)
  where
    (_, b0) = last xs

    insides ((_, b):xs@((a, _):_)) = (b, a) : insides xs
    insides _                      = []

redistributeOut :: (a, [(b, a)], b) -> [(a, b)]
redistributeOut (a0, xs, b0) = outsides a0 xs b0
  where
    outsides a_i ((b_i, a_j):xs) b_z = (a_i, b_i) : outsides a_j xs b_z
    outsides a   []              b   = (a  , b  )

merge :: [(Int, Int)] -> [(Int, Int)]
merge [] = []
merge xs = redistributeOut . second (filter (not . adjacent)) . fromJust . redistributeIn $ xs
  where
    second f (a, b, c) = (a, f b, c)

    adjacent (a, b) = a + 1 == b