從時間跨度的名單（不包括在列表中的跨度）

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)