假設我有一個鍵串列， k = [2,3,7,15,18,23]; 和節點串列， n = [1,5,10,15,20]。兩個串列都是排序串列。
那么“最近的下一個節點”，或者 key 的后繼節點 k = 2 是 n = 5; 因為 k = 3 是 n = 5；因為 k = 7 是 n = 10，等等。如果鍵值大于最后一個節點值，則其后繼節點是第一個節點元素，k = 23也是n = 1。我想輸出一個串列陣列，該陣列將每個后繼節點與其鍵的格式進行映射[[successor_node1, key, key],[successor_node2, key, key],...]。所以結果例如是output_array = [[5,2,3],[10,7,],[15,15],[20,18],[1,23]]
我怎樣才能在一個函式中用 F# 實作這些？
uj5u.com熱心網友回復：
您可以通過撰寫一個遞回函式來執行此操作，該函式遍歷兩個串列并在第一個元素上進行模式匹配。為了保持結果，最好的選擇可能是使用不可變映射 - 在你進行時，您可以為與各個后繼節點關聯的各個鍵添加值：
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
uj5u.com熱心網友回復：
我想出了一個新的解決方案來解決您對問題的描述，而不是試圖修改您的代碼。我使用了一種完全不同的方法：沒有可變變數或資料結構，只有帶有一個遞回函式的純函式代碼。我這樣做是因為它對我來說更容易，而不是因為純代碼總是更好。
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
一般方法是使用遞回回圈，顯式傳遞所有所需的輸入狀態，而不是使用可變變數。acc還通過一個累加器來收集輸出。
此代碼使用 a List.takeWhile，后跟List.skip同一串列中的 a 。這有點低效。如果List.splitWhenF# 庫中有一個函式，或者您自己撰寫一個函式，則可以改進它。
uj5u.com熱心網友回復：
除了之前提出的建議之外，還有一次嘗試 :) 我不太熟悉 F# 標準庫和習慣用法，所以它可能不是習慣用語/次優/兩者，但我嘗試以一種非常直接的方式解決它（因為我將口頭解釋解決方案）：
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]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/347686.html