Say I have a list of keys, k = [2,3,7,15,18,23] ; and a list of nodes, n = [1,5,10,15,20] . Both lists are sorted lists.

Then the "closest next node", or the successor node for key k = 2 is n = 5 ; for k = 3 is n = 5; for k = 7 is n = 10 , and so on. If the key value is greater than the last node value, then its successor node is the first node element, so k = 23 is n = 1. I want to output a list array that maps each successor nodes with their keys in format [[successor_node1, key, key],[successor_node2, key, key],...]. So the results for example is output_array = [[5,2,3],[10,7,],[15,15],[20,18],[1,23]]

how can I achieve these with F# in just ONE function?

CodePudding user response：

You can do this by writing a recursive function that iterates over the two lists and pattern matches on the first elements. To keep the result, the best option is probably to use an immutable map - as you go, you can add the values for the individual keys associated with individual successor nodes:

let k = [2;3;7;15;18;23] 
let n = [1;5;10;15;20]

let rec findSuccessors first res k n =
  // Add a key 'k'  associated with a successor node 'n' to the list
  let add k n = 
    match Map.tryFind n res with
    | None -> Map.add n [n; k] res
    | Some l -> Map.add n (l @ [k]) res
  match k, n with 
  | [], _ ->  
    // If there are no more keys, we return the results
    res |> Map.toList |> List.map snd
  | k::ks, [] -> 
    // If there are no more successors, use the special 'first'
    findSuccessors first (add k first) ks []
  | k::ks, n::ns when n < k -> 
    // If we have a key 'k', but the next node is smaller, skip it
    findSuccessors first res (k::ks) ns
  | k::ks, n::ns -> 
    // Found a key 'k' with a successor 'n' - add it to the list
    findSuccessors first (add k n) ks (n::ns)

findSuccessors (List.head n) Map.empty k n

CodePudding user response：

I came up with a new solution to your description of the problem, rather than trying to modify your code. I'm using quite a different approach: no mutable variables or data structures, just pure functional code with one recursive function. I did this because it was easier for me, not because pure code is always better.

let mapNodes startingNodes startingKeys =
    let rec loop remainingNodes remainingKeys acc =
        match remainingNodes, remainingKeys with
        | _, [] ->
            acc
        | [], keys ->
            let next = startingNodes |> List.tryHead |> Option.map (fun firstNode -> firstNode :: keys)
            match next with
            | Some next -> next :: acc
            | None -> acc // this shouldn't happen if there is at least one starting node
        | nextNode :: restNodes, keys ->
            let keysForNode = keys |> List.takeWhile (fun key -> key <= nextNode)
            match keysForNode with
            | [] ->
                loop restNodes keys acc
            | keysForNode ->
                let next = nextNode :: keysForNode
                let restKeys = keys |> List.skip keysForNode.Length
                loop restNodes restKeys (next :: acc)

    loop (startingNodes |> List.tail) startingKeys [] |> List.rev

let nodes = [ 1; 5; 10; 15; 20 ]
let keys = [ 2; 3; 7; 15; 18; 23 ]
let expected = [ [ 5; 2; 3 ]; [ 10; 7 ]; [ 15; 15 ]; [ 20; 18 ]; [ 1; 23 ] ]

let result = mapNodes nodes keys // [[5; 2; 3]; [10; 7]; [15; 15]; [20; 18]; [1; 23]]
result = expected // true

The general approach is to use a recursive loop that explicitly passes through all of the input state required, rather than using mutable variables. An accumulator acc is also passed through to gather the output.

This code uses a List.takeWhile, followed by a List.skip on the same list. This is slightly inefficient. It could be improved if there was a List.splitWhen function in the F# library, or if you were to write one yourself.

CodePudding user response：

One more attempt in addition to what was proposed earlier :) I'm not well familiar with F# standard library and idioms, so it might be not idiomatic/suboptimal/both, but I tried to solve it in a very straightforward way (as I would explain the solution verbally):

let nearest_keys_per_node keys nodes =
  (* Simple helper function that finds the nearest next node for a given key *)
  let nearest_next_node nodes k =
    match nodes with
      | [] -> failwith "Empty nodes list!"
      | hd :: tl ->
        let rec nearest_node_tr k current_best = function
          | [] -> current_best
          | hd :: tl when hd < k -> nearest_node_tr k current_best tl
          | hd :: tl -> hd
        nearest_node_tr k hd tl

  List.map (nearest_next_node nodes) keys (* Get the nearest next node for each key *)
  |> List.zip keys                        (* "Glue" them together with the keys - gettin a list of tuples (key, node) *)
  |> Seq.groupBy (fun (_, node) -> node)  (* Group by nodes*)
  |> List.ofSeq
  |> List.map (fun (node, seq) ->         (* "Cleanup" the structure that we got after the grouping and transform in to your desired output *)
      node :: (List.ofSeq(seq) |> List.map fst)
    )
;;

> nearest_keys_per_node [2;3;7;15;18;23] [1;5;10;15;20];;
val it : int list list = [[5; 2; 3]; [10; 7]; [15; 15]; [20; 18]; [1; 23]]