Merging lists of 'spatial' tuples

Question

I have three lists of tuples, each tuple contains (startpos, endpos, value).

What I want to do is merge these into one list of tuples (startpos, endpos, values[]), but following a rule which I find it easier to draw than to write:

//third               [---------]                    [------------]
//second        [-------------]              [---------------------------]
//first   [-----------------------------]    [--------------]
//(pos)   0123456789|123456789|123456789|123456789|123456789|123456789|123456789
//result  [--1-][--2-][---3---][---1----]    [---2--][---3--]

(The numbers in result represent the expected length of the values[] list for each resulting element)

Basically, I only keep a 'higher' element where it overlaps a 'lower' element, and I split up into 'homogenous' elements.

The positions can be considered as being of type int. As you can see from the result, the 'split' segments do not start and end at the same position, but at pos-1 or pos+1. The order of the values is not important, as long as it is defined.

Sample data (based on example above):

let third =  [(12,22,3.1);(43,56,3.2)]
let second = [(6,20,2.1);(35,63,2.2)]
let first =  [(0,30,1.1);(35,50,1.2)]
let after =  [
                (0,5,[1.1]);
                (6,11,[1.1;2.1]);
                (12,20,[1.1;2.1;3.1]);
                (21,30,[1.1]);
                (35,42,[1.2;2.2]);
                (43,50,[1.2;2.2;3.2])
             ]

Right now I'm finding it difficult to think about this in a functional way, anything that comes to mind is imperative. Maybe that's inevitable in this case, but if anyone has any ideas...

UPDATE Actually, if we generalised the input case to already be of type (int*int*List<float>), we could just treat the case of two input lists, then fold that.

PS: This is not homework, or code golf, I've just sterilised the data somewhat.

Answer 1

Your after data is wrong; at least my program thinks it is, and I believe it. :)

let third =  [(12,22,3.1);(43,56,3.2)] 
let second = [(6,20,2.1);(35,63,2.2)] 
let first =  [(0,30,1.1);(35,50,1.2)] 

let all = List.concat [first; second; third]
let min = all |> Seq.map (fun (x,y,z)->x) |> Seq.min 
let max = all |> Seq.map (fun (x,y,z)->y) |> Seq.max

let setsEachValueIsIn =
    [min..max] 
    |> List.map (fun i -> 
        i, all 
            |> List.filter (fun (x,y,z) -> x<=i && i<=y) 
            |> List.map (fun (x,y,z) -> z))

printfn "%A" setsEachValueIsIn

let x1,l1 = Seq.nth 0 setsEachValueIsIn

let result = 
    setsEachValueIsIn 
    |> List.fold (fun (((l,h,s)::t) as prev) (nx,ns) -> 
                    if s=ns then (l,nx,s)::t else (nx,nx,ns)::prev
                ) [x1,x1,l1]
    |> List.rev

let after =  [ 
                (0,5,[1.1]); 
                (6,11,[1.1;2.1]); 
                (12,20,[1.1;2.1;3.1]); 
                (21,30,[1.1]); 
                (35,42,[1.2;2.2]); 
                (43,50,[1.2;2.2;3.2]) 
             ] 

printfn ""
printfn "%A" result
printfn ""
printfn "%A" after
assert(result = after)

Strategy: first I map every number in the whole range to the 'sets it is in'. Then I fold, seeding with the first result as (min,min,setsMinIsIn) and every step of the way, if the set does not change, I just widen the range, else if the set does change, I make a new element.

Key for var names in the fold: low, high, set, nx-next x, ns-next set

Answer 2

Complete rewrite (see edits), shorter, more elegant, maybe less readable. Still pinching Brian's logic.

UPDATE: now works, at least for the test above

let third =  [(12,22,3.1);(43,56,3.2)]
let second = [(6,20,2.1);(35,63,2.2)]
let first =  [(0,30,1.1);(35,50,1.2)]

//===helper functions===
// foldable combined min and max finder
let minmax (mn,mx) (x,y,_) = (min mn x, max mx y)  
// test if x - y range overlaps position i
let overlaps i (x,y,_) = x<=i && i<=y 
// get third element from triple
let getz (_,_,z) = z              

//specialise function, given two tuples, will combine lists (L & U)
//  but only if both lists have contents AND their indexes (il & iu) 
//  are not more than 1 apart, i is included simply so that we can pass 
//  merge directly to the List.map2 below
let merge (i,il,L) (_,iu,U) = 
     if L = [] || U = [] || iu - il > 1 then 
        (i, il, L) 
     else  
        (i, iu, L @ U)

let input = [first;second;third] // input data - 'bottom' first
//find max and min positions
let (x0,yn) = input |> Seq.concat |> Seq.fold minmax (0,0) 

//transform each data list to a list of (i,[z])
let valsByPos = input |> List.map (fun level -> //for each data 'level' 
                [x0..yn] |> List.map (fun i ->   //for each position in range
                     //collect values of all elements in level that
                     // overlap this position
                     (i, level |> List.filter (overlaps i) |> List.map getz)))

// 'merge up' each level, keeping only upper values if lower values exist
// after we will have just one list of (i, [z])
let mergedValsByPos = valsByPos //offside here for SO formatting
          //add an index into each tuple
          |> List.mapi (fun i l -> l |> List.map (fun (j,z) -> (j,i,z)))  
          //use index to determine if we should 'merge up' for each subsublst
          |> List.reduce (List.map2 merge) 
          //rip the index back out                     
          |> List.map (fun (i,_,z) -> (i,z)) 

//get first value as seed for fold
let x1,l1 = Seq.nth 0 mergedValsByPos

//transform list (i,[z]) into list of (x,y,[z])
//key: (l)ow, (h)igh, (s)et, (nx)-next x, (ns)-next set
let result = 
    mergedValsByPos 
    //first remove any positions where there are no values
    |> List.filter (fun el -> snd(el) <> [])
    //double capture on state so we can take all or part of it
    |> List.fold (fun (((l,h,s)::t) as prev) (nx,ns) -> 
                    //if [z] value hasn't changed, we just enlarge range
                    //  of current state (from (l,h) to (l,nx)) 
                    //  otherwise we add a new element (nx,nx,ns) to state
                    if s=ns then (l,nx,s)::t else (nx,nx,ns)::prev 
                ) [x1,x1,l1] //initial state from seed values
    |> List.rev //folded value is backwards (because of::), so reverse