Search code examples
functional-programmingsml

functional programming (specifically SML) list interval question

I have a problem where given two lists representing schedules (periods when someone is busy), I want to return the available times for when both people/lists are available. For example,

create_schedule([(1,2), (4,6), (8, 12)], [(1,3), (5,9)]] => [(0, 1), (3,4)]

All times start from 0 and go up to the max number given in the input. This is my approach:

  1. Use the List.concat function in order to flatten the list. So, the input becomes [(1,2), (4,6), (8, 12), (1,3), (5,9)].
  2. Sort by the first item in each tuple => [(1,2), (1,3), (4, 6), (5,9), (8,12)].
  3. Merge the intervals so it becomes [(1,3), (4, 12)].
  4. Take the numbers in between each tuple. For this particular example, I need to insert a (0,0) tuple in the beginning. So for [(0,0), (1,3), (4,12)], the middle values are (0, 1) and (3,4) and that's the answer.

I can't use recursion and my solution has to be in O(nlogn). I've already coded the merge and sort function. Now, I need to create a function that takes the middle values so [(0,0), (1,3), (4,12)] becomes [(0, 1), (3,4)] (the answer). I'm not sure how to do this without recursion. I'm supposed to use higher-order functions like map, foldl, foldr, filter, etc.. I feel like I have a good start so far but I'm having a lot of trouble finishing it. Any tips would be super helpful!

Solution

  • I need to create a function that takes the middle values so [(0,0), (1,3), (4,12)] becomes [(0, 1), (3,4)] (the answer).

    One approach: starting with [(0,0), (1,3), (4,12)], you can use List.tl and ListPair.zip to get [((0,0),(1,3)), ((1,3),(4,12))]. Then you just need a function that takes ((0,0),(1,3)) to (0,1) and ((1,3),(4,12)) to (3,4).

    Another approach: rather than inserting (0,0) at the start of the list, you can use (0, nil) as the init value in a call to List.foldl. The f will have type (int * int) * (int * int list), and will take ((1,3),(0,nil)) to (3,[(0,1)]) and ((4,12),(3,[(0,1)])) to (12,[(3,4),(0,1)]). You'll end up with (12,[(3,4),(0,1)]), whence you can easily obtain [(0,1),(3,4)].