Group overlapping intervals, in Elm

groupOverlaps.elm

import Html exposing (text)

main =
  text <| toString <| group data
  
type alias Interval = (Int, Int)

data =
  [ (1, 2), (3, 5), (4, 10), (5, 8), (5, 12), (13, 15), (14, 20)]

group : List Interval -> List (List Interval)
group pairs =
  List.foldl combine [] pairs

combine : Interval -> List (List Interval) -> List (List Interval)
combine interval groups =
  case groups of
    [] ->
      [[interval]]
    (first :: rest) ->
      if overlapGroup interval first then
        (interval :: first) :: rest 
      else
        first :: combine interval rest

overlapGroup : Interval -> List Interval -> Bool
overlapGroup interval group =
  List.any (overlapInterval interval) group
  
{- Do the two intervals overlap? This assumes that intervals are half-open
 (include beginning value but not end value) and for each interval the begin
 value is less than the end. -}
overlapInterval : Interval -> Interval -> Bool
overlapInterval (b1, e1) (b2, e2) =
  if e1 <= b2 || e2 <= b1 then False else True