[Haskell-cafe] Suggestion for Data Structure regarding Timetabling and Time Intervals

[dominic at steinitz.org]

I don’t know if this is relevant but for manipulating time intervals, I have found the intervals package very useful.

> Message: 5
> Date: Wed, 2 Nov 2016 21:26:32 +0100
> From: Olaf Klinke <olf at aatal-apotheke.de>
> To: list at mroth.net
> Cc: haskell-cafe at haskell.org
> Subject: Re: [Haskell-cafe] Suggestion for Data Structure regarding
> 	Timetabling and Time Intervals
> Message-ID: <63753058-716B-4D2B-8D8F-4B0F77732C2A at aatal-apotheke.de>
> Content-Type: text/plain; charset=us-ascii
> 
> Dear Michael,
> 
> if you can be sure your intervals will never overlap, why not use a binary search tree, such as Data.Set from containers? You could make a data structure distinguishing major and minor intervals such as:
> 
> type Time = -- your favourite totally ordered time type
> data Major = Major {
>  fromTime :: Time,
>  untilTime :: Time} deriving (Eq)
> data Minor = Minor {
>  after :: Time
>  before :: Time} deriving (Eq)
> type TimeInterval = Either Minor Major
> 
> instance Ord (Either Minor Major) where
>   Left  a <= Left  b = before a <= after b
>   Right a <= Right b = untilTime a <= fromTime b
>   Left  a <= Right b = before a <= fromTime b
>   Right a <= Left  b = untilTime a <= after b
> 
> If I understood your intentions correctly, inserting a minor interval between a :: Major and b :: Major where a < b would mean to insert 
> 
> Minor {after = untilTime a, before = fromTime b}
> 
> It might also be handy to define a new type (isomorphic to the product (a,b))
> 
> Anno a b = Anno a b
> 
> whose Ord instance uses the Ord instance of b only, so that 
> 
> Anno "Some annotation" (Major t0 t1)
> 
> is an interval bearing some annotation that can be ordered just like the Major type.
> 
> If your intervals _do_ overlap, then two intervals can be in six different configurations (instead of LT, GT and EQ), and several tree structures exist that support some operations more or less efficiently. Bioinformatics and geometry has developed good data structures and algorithms to deal with efficient overlap searches. 
> 
> Olaf
> 
> 

Dominic Steinitz
dominic at steinitz.org
http://idontgetoutmuch.wordpress.com