haskell - 如果给定一个表示范围的元组列表，你如何合并连续的范围？

Question

如果给定一个表示范围的元组列表，如下所示:

[(0,10),(10,100),(1000,5000)]

我想合并表示连续范围的元组，所以结果是这样的:

[(0,100),(1000,5000)]

任何优雅的解决方案？

这是我的

mergeRanges :: [(Int, Int)] -> [(Int, Int)]
mergeRanges xs = foldr f [] (sort xs)
  where f new@(x,y) acc@((a,b):ys) =
            if y == a
            then (x,b):ys
            else new:acc
        f x acc = x:acc

编辑:范围不重叠

Answer 1

除非这是一种在您的程序中更频繁出现的模式，否则我会选择直接递归(后面是未经测试的代码!):

mergeRanges (lo1,hi1) : (lo2,hi2) : rest)
    | hi1 == lo2 = mergeRanges ((lo1,hi2) : rest) 
             -- or (lo1,hi2) : mergeRanges rest, to merge only adjacent ranges
mergeRanges (interval:rest) = interval : mergeRanges rest
mergeRanges [] = []

(您可以通过使用 @-patterns 来优化一点，但代价是困惑)。

但如果你真的想，你可以使用下面的辅助函数

 merge :: (a -> a -> Maybe a) -> [a] -> [a]
 merge f [] = []
 merge f [x] = [x]
 merge f (x:y:xs) = case f x y of
     Nothing -> x : merge f (y:xs)
     Just z -> merge (z:xs) -- or z : merge xs

并作为第一个参数给出

 merge2Ranges (lo1, hi1) (lo2, hi2) 
     | hi1 == lo2 = Just (lo1, hi2)
     | otherwise = Nothing

我怀疑 merge 是否在某处的库中，因为它非常针对手头的问题。