{-# OPTIONS -Wall #-} module Main where import Data.List (sort) import Data.List.NonEmpty (NonEmpty(..)) data Iv a = Iv a a deriving (Show, Eq, Ord) -- Actually it doesn't matter how Iv a b and Iv a c are sorted relative to each other -- Returns all gaps between outermost endpoints of a list of intervals gaps :: Ord a => [Iv a] -> [Iv a] gaps = gaps' . sort -- Returns all gaps between outermost endpoints of a list of intervals, assuming sorted gaps' :: Ord a => [Iv a] -> [Iv a] gaps' [] = [] gaps' (iv:ivs) = case getBlock (iv :| ivs) of (_, []) -> [] (Iv _ to, rest@(Iv next _ : _)) -> Iv to next : gaps' rest -- Returns first contiguous block and remaining intervals, assuming sorted getBlock :: Ord a => NonEmpty (Iv a) -> (Iv a, [Iv a]) getBlock (iv :| []) = (iv, []) getBlock (Iv a b :| Iv c d : rest) | c <= b = getBlock (Iv a d :| rest) | otherwise = (Iv a b, Iv c d : rest) main :: IO () main = do print $ gaps @Int [Iv 2 3, Iv 4 5, Iv 0 3]