代表一個類似於後繼者列表的「圖形」

Question

我有一個列表，表示節點（邊）之間的連接在一個ipotetically圖中;列表的結構類似於該：

val def_graph : ((int * int) * (int * int)) list = 
[((0, 0), (2, 1)); ((0, 0), (1, 2)); ((0, 1), (2, 0)); ((0, 1), (2, 2)); 
((0, 1), (1, 3)); ((0, 2), (2, 1)); ((0, 2), (2, 3)); ((0, 2), (1, 0)); 
((0, 2), (1, 4)); ((0, 3), (2, 2)); ((0, 3), (2, 4)); ((0, 3), (1, 1)); 
((0, 3), (1, 5)); ((0, 4), (2, 3)); ((0, 4), (2, 5)); ((0, 4), (1, 2)); 
((0, 4), (1, 6)); ((0, 5), (2, 4)); ((0, 5), (2, 6)); ((0, 5), (1, 3)); 
((0, 5), (1, 7)); ((0, 6), (2, 5)); ((0, 6), (2, 7)); ((0, 6), (1, 4)); 
((0, 7), (2, 6)); ((0, 7), (1, 5)); ((1, 0), (3, 1)); ((1, 0), (0, 2)); 
((1, 0), (2, 2)); ((1, 1), (3, 0)); ((1, 1), (3, 2)); ((1, 1), (0, 3)); 
((1, 1), (2, 3)); ((1, 2), (3, 1)); ((1, 2), (3, 3)); ((1, 2), (0, 0)); 
((1, 2), (0, 4)); ((1, 2), (2, 0)); ((1, 2), (2, 4)); ((1, 3), (3, 2)); 
((1, 3), (3, 4)); ((1, 3), (0, 1)); ((1, 3), (...)); ...] 

其中節點是由元組rapresented（（0,0）是一個節點，（1,3）是一個節點...等）和（（0 ，0），（2,1））表示節點（0,0）和節點（2,1）之間的連接;

如何用任何節點的後繼列表來表示我的「圖形」？ 結果必須是：

val succ_graph : ((int * int) * (int * int) list) list = 
[((0,0),[(2,1),(1,2)]);((0,1),[(2,0),(2,2),(1,3)]);((0,2),[(2,1),(2,3), 
(1,0),(1,4)]); .... ] 

元組的列表，其中第一個參數是節點本人和第二參數是對他的任何後續的列表;

我寫了一個函數，提取後繼給出一個特定的節點的列表，但我不知道如何做其餘的。

let succ arcs node = 
    let rec aux = function 
    [] -> [] 
    | (x,y)::rest -> if x = node then y::aux rest 
     else aux rest 
    in aux arcs;; 

對不起，但這是我第一次使用ocaml，對不起英文不好！

謝謝。

Answer 1

作爲初步評論，您的問題陳述和示例有點令人困惑。您提供的示例結果不是您所說的類型。而且你的函數也不計算類型的一部分。比方說，你真的想要這個類型：

((int * int) * ((int * int) * (int * int)) list) list 

對於您想要的對節點列表您的圖中的每個節點。這方面的一個例子是：

[((0, 0), [((0, 0), (2, 1)); ((0, 0), (1, 2))]); ... ] 

你們的榜樣結果不會是這樣的，你的函數計算的節點列表（而不是成對的節點列表）。

所以第一件要做的事可能是解決這個分歧。

在你弄明白了之後，你現在的代碼實際上非常接近正確的答案。您不必查找特定節點的鏈接，而是將您看到的所有鏈接添加到答案中。您不需要將答案放在列表的前面，您需要能夠在您正在構建的結果中插入答案。

那麼開始的好地方可能是編寫代碼來爲((int * int) * ((int * int) * (int * int)) list) list類型的累計結果添加新鏈接。

OCaml中的列表是不可變的，所以要做到這一點的方法是構造一個新列表。新列表將包含舊列表的許多部分;你不必從頭開始構建它。 （這一點，事實上，爲什麼不可變的數據是在實踐中實際可用。）

更新

正如我說的，你可以，如果你寫一個函數，在增加了一個新的繼任者使用當前的代碼正確的地方。然後，您使用這個新功能，而不是您現在使用的簡單功能::。

但是，將某種東西添加到不可變結構中的概念起初有點棘手。

這裏有一個函數，它在將列表「保存」列表的同時「添加」到列表中。即，它返回一個具有所需屬性的新列表。舊的列表是不變的（不變的，這是給定的）。

let rec insert l x = match l with 
| [] -> [x] 
| h :: t -> if x <= h then x :: l else h :: insert t x 

它看起來像這樣：

# insert [1; 1; 3; 4; 5; 9] 2;; 
- : int list = [1; 1; 2; 3; 4; 5; 9] 

您可以使用此插入功能排序列表（低效率）：

let rec sort = function 
| [] -> [] 
| h :: t -> insert (sort t) h 

它看起來像這樣：

# sort [3; 1; 4; 1; 5; 9; 2];; 
- : int list = [1; 1; 2; 3; 4; 5; 9] 

這實質上就是你想要做的，e除了你有配對而不是整數，你的結構比排序列表更復雜一些。