从时间跨度的名单（不包括在列表中的跨度）

Question

我有时间跨度（表示为整数元组）名单确定的时间间隔，如：

timespans = [ (1200, 1210) 
     , (1202, 1209) 
     , (1505, 1900) 
     , (1300, 1500) 
     , (1400, 1430) 
     ] 

我想找到一个优雅的Haskell解决方案来确定时间间隔，而时间间隔不在列表中。

Answer 1

首先我会按照他们的开始时间对跨度进行排序。然后你可以很容易地合并重叠的跨度。一旦你有了，你可以通过迭代合并跨度（通过拖拽它的尾部）来找到差距。差距将是从第一个项目的结束时间到第二个项目的开始时间的跨度。

在这段代码应该是这样的：

mergeSortedSpans [] = [] 
mergeSortedSpans ((from1, to1):(from2, to2):spans) | to1 >= from2 = 
    mergeSortedSpans $ (from1, max to1 to2):spans 
mergeSortedSpans (span:spans) = span : mergeSortedSpans spans 

inPairs _ [] = [] 
inPairs f (x:xs) = zipWith f (x:xs) xs 

gap (_, to1) (from2, _) = (to1, from2) 

gaps = inPairs gap . mergeSortedSpans . sort 

用法：

gaps timespans 
-- [(100,500),(1210,1300),(1500,1505)] 

Answer 2

我的解决方案与分而治之的作品融化所有重叠的时间跨度，以获得非重叠时间跨度的排序列表：

module Test 
where 

type Time = Int 
type Start = Time 
type Stop = Time 
type Span = (Start, Stop) 

timespans :: [Span] 
timespans = [ (1200, 1210) 
      , (1202, 1209) 
      , (1505, 1900) 
      , (1300, 1500) 
      , (1400, 1430) 
      , (500,1200) 
      , (20,100) 
      ] 


flattentime :: [Span] -> [Span] 
flattentime [] = [] 
flattentime [x] = [x] 
flattentime (s:ss) = combine (flattentime [ times | times <- ss, (fst times) < (fst s) ]) s 
          (flattentime [ times | times <- ss, (fst times) >= (fst s) ]) 

combine [] s [] = [s] 
combine [] s ss2 = melt s (head ss2) ++ tail ss2 
combine ss1 s [] = firsts ss1 ++ melt (last ss1) s 
combine ss1 s ss2 = (firsts ss1) ++ melt3 (last ss1) s (head ss2) ++ (tail ss2) 
melt (x1,x2) (x3,x4) | x2 < x3 = [(x1,x2), (x3,x4)] 
        | x4 < x2 = [(x1,x2)] 
        | otherwise = [(x1,x4)] 

melt3 (x1,x2) (x3,x4) (x5,x6) = if (length ss >1) then (head ss):(melt y (x5,x6)) else melt y (x5,x6) 
         where ss = melt (x1,x2) (x3,x4) 
          y = last ss 

firsts [x] = [] 
firsts [] = [] 
firsts (x:xs) = x:(firsts xs) 

它没有那清新典雅我希望这将是。 ..任何人有一个更短的解决方案呢？

Answer 3

感谢sepp2k - 您的权利;它更容易你建议的方式！在工作哈斯克尔码：

flattentime :: [(Integer,Integer)] -> [(Integer,Integer)] 
flattentime [] = [] 
flattentime [x] = [x] 
flattentime ((x1,x2):(y1,y2):ts) | y2<x2 = (x1,x2):(flattentime ts) 
           | y1<x2 = (x1,y2):(flattentime ts) 
           | otherwise = (x1,x2) : (flattentime ((y1,y2):ts)) 

以后我就只要致电：

> (flattentime.sort) timespans 

Answer 4

优雅 - 你的意思是什么样的？

import Data.List 
timespans = [ (1200, 1210) 
     , (1202, 1209) 
     , (1505, 1900) 
     , (1300, 1500) 
     , (1400, 1430) 
     ] 

gaps xs0 = filter g $ zipWith f xs (tail xs) where 
    xs = merge $ sort xs0 
    f (_, t0) (t1, _) = (t0, t1) 
    g (t0, t1) = t0 < t1 
    merge [] = [] 
    merge ((t0, t1):(t2, t3):ys) | t2 < t1 = merge ((t0, max t1 t3) : ys) 
    merge (y:ys) = y : merge ys 

main = print (gaps timespans)