Public Group

# Functional Programming - generating lists based on values

This topic is 2733 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

This isn't homework, but is for learning so I'm looking for help more than a solution.

The problem is I have a timeframe (start/duration) and a list of timefames that represent 'taken' times for something like a schedule/calendar. I'm looking to convert those into a list of 'open' timeframes, and am kinda stuck about how to do that in a nice functional way.

Working in F# if it matters.

##### Share on other sites
I'd say this problem is slightly trickier than it looks at first.

An elegant way to do this is to define a closed algebra on intervals with the operations union, complement and intersection: you can formulate your problem as intersection(big_timeframe, complement(union(taken_timeframes))).

This can be done in an optimal way in a functional language using scanline-type algorithms on lists, or slightly less optimally and more clearly using the scanline idea and an intermediate datastructure that partitions the intervals into disjoint subintervals pointing to their containing parent intervals. I'd opt for the latter.

You can build these operations easily using the following method:

Notation: {A, B} is a tuple representing an interval, A <= B. {} means tuple, [] means list.

1) Decompose intervals into [{Endpoint, Parent_interval}, ...]. Eg. the interval {A, B} is decomposed into the list [{A, {A, B}}, {B, {A, B}}].

2) Sort this based on Endpoint.

3) Use these endpoints to build disjoint subintervals which know their containing parent intervals, your datastructure is [{Subinterval, Parent_intervals_set}, ...]. 2) and 3) is basically a 1-d scanline algorithm.

4) Find the subintervals that satisfy your predicate (union, intersection, complement). For example, union simply means find subintervals whose Parent_interval_set is nonempty. The filter hof is useful for expressing these.

5) Merge contiguous subintervals.

6) ???

7) Profit.

This can be optimized by writing union, intersection and complement directly without going through
the subintervals indirection, but that's wordier and trickier.

##### Share on other sites
I must say, that wasn't very clear, and while I think I completely missed what you were trying to say (and suspect that simple set operations won't work on continuous timeframes without re-implementing essentially this code) it did kind of nudge me towards breaking the timeframe into progressively smaller ones rather than filling a collection of results.

Anyways, this slapdash newb F# appears to do what I was looking for. Critiques and criticisms are certainly welcome.
 type event = { start:int duration:int } with override this.ToString() = System.String.Format("start: {0}, duration: {1}",this.start,this.duration) let endOf a = a.start + a.duration let containedIn a b = if b.start <= a.start && endOf b >= endOf a then true else false let collidesWith a b = if (a.start >= b.start && a.start < endOf then true elif (endOf a > b.start && endOf a < endOf then true else false let nextOpenTime timeframe events = List.min ((endOf timeframe) :: (List.filter (fun x -> List.forall (fun y -> not (collidesWith {start=x;duration=0} y)) events) (List.filter (fun i -> i >= timeframe.start) [timeframe.start..endOf timeframe]))) let rec openSlots timeframe events = let result = {start = timeframe.start; duration = match List.minBy (fun i -> i.start) (List.filter (fun i -> i.start >= timeframe.start) events @ [{start = endOf timeframe; duration = (endOf timeframe - timeframe.start)}]) with | y when y.start = endOf timeframe -> timeframe.duration | x -> x.start-timeframe.start } if endOf result = endOf timeframe then if result.duration = 0 then [] else [result] else let x = nextOpenTime {start = endOf result; duration = endOf timeframe - endOf result} events if x = endOf timeframe then if result.duration = 0 then [] else [result] else if result.duration = 0 then openSlots {start = x; duration = endOf timeframe - x} events else result :: openSlots {start = x; duration = endOf timeframe - x} events 

##### Share on other sites
You don't have to use an if to return true or false from a boolean espression. You can directly use the boolean expression (negating it in case of need). So

let containedIn a b = if b.start <= a.start && endOf b >= endOf a then true else false

can be simply written as

let containedIn a b = b.start <= a.start && endOf b >= endOf a

and so on. This is valid in every language, not just F# (which I actually don't know very well). More trickier is the collidesWith function which may become

let collidesWith a b = (a.start >= b.start && a.start < endOf || (endOf a > b.start && endOf a < endOf

##### Share on other sites
You're right, I was less than clear. The nudge I expected to give was to look at sweepline algorithms but I wrote scanline instead. Sorry.

I don't know F#, but that algorithm looks quadratic (it seems you're applying min operations to the list for every interval).

Here's another stab at an explanation with accompanying Haskell code.

Suppose you have a list of intervals that contains the occupied intervals AND the interval representing the timeframe.

You can partition the initial, overlapping, set of intervals into a set of disjoint intervals. If these disjoint intervals keep track of how many parent intervals overlap them, you can easily discard those with a > 1 overlap; the remaining intervals are free. This generalises to other interesting interval operations if you keep track of more than number of overlapping parents: this is where I was coming from.

You can accomplish this in O(nlogn) time or O(n) time if you get to use a non-comparison sort like radix sort. HOW you accomplish this is by first decomposing intervals into their endpoints, sorting them, and sweeping over these to generate subintervals and overlap counts.

Once you've done this, all that remains is to filter out those intervals with intersection counts > 1. The same approach works for many other interval-related problems.

 import Data.List data Interval a = In a a Int deriving ( Show ) data Point a = Pt a Int deriving ( Show ) decompose = concat . map (\(In a b _) -> [Pt a 1, Pt b (-1)]) disjoint [] = [] disjoint (Pt a e:xs) = disjoint_h e a xs disjoint_h _ _ [] = [] disjoint_h accum a (Pt b e:rest) = In a b accum: disjoint_h (accum + e) b rest cmp (Pt a _) (Pt b _) = compare a b prune_empty_intervals = filter (\(In a b _) -> a /= build_disjoint :: [Interval Int] -> [Interval Int] build_disjoint = prune_empty_intervals . disjoint . (sortBy cmp) . decompose to_internal = map (\(a, -> In a b 1) from_internal = map (\(In a b accum) -> (a, ) find_free = from_internal . find_free_h . to_internal find_free_h intervals = filter (\(In _ _ accum) -> accum == 1) (build_disjoint intervals) 

So, let's say we have a timeframe of 1 to 10 and a few occupied intervals:

 *Main> find_free [(1, 10), (1,2), (3, 6), (7, 9)] [(2,3),(6,7),(9,10)] *Main> 

edit: removed comments, highlighting makes the code with them harder to read

##### Share on other sites
Heh, the forum software mysteriously decided to uppercase some variable names in the code section above, breaking stuff.

1. 1
2. 2
3. 3
4. 4
frob
15
5. 5

• 16
• 12
• 20
• 12
• 18
• ### Forum Statistics

• Total Topics
632160
• Total Posts
3004497

×