OCaml：解析JSON到循環類型

Question

這個問題與another question有關我之前問過。

我正在從JSON文件中讀取數據，並嘗試將它們解析爲我製作的數據類型。對於房間

{ 
    "rooms": 
    [ 
    { 
     "id": "room1", 
     "description": "This is Room 1. There is an exit to the north.\nYou should drop the white hat here.", 
     "items": ["black hat"], 
     "points": 10, 
     "exits": [ 
     { 
      "direction": "north", 
      "room": "room2" 
     } 
     ], 
     "treasure": ["white hat"] 
    }, 
    { 
     "id": "room2", 
     "description": "This is Room 2. There is an exit to the south.\nYou should drop the black hat here.", 
     "items": [], 
     "points": 10, 
     "exits": [ 
     { 
      "direction": "south", 
      "room": "room1" 
     } 
     ], 
     "treasure": ["black hat"] 
    } 
    ] 
} 

我的用戶定義類型是：

type room = { 
    room_id   : int ; 
    room_description : string ; 
    room_items  : item list ; 
    room_points  : int ; 
    room_exits  : exit list ; 
    room_treasure : item list ; 
} 
and exit = direction * room 

然而，房間有一個「退出」字段，它本身就是一個「房間」類型。然後，當我嘗試創建記錄room1時，我首先需要定義room2，但爲了定義room2，我需要知道room1。這看起來像循環類型。

任何人都可以幫助我嗎？

Answer 1

如果你堅持OCaml的不可變和渴望的子集，沒有真正的方法來建立任意的循環結構。問題和你說的一樣。

可以使用let rec構建循環結構的具體示例，但我不認爲這可以擴展到構建任意結構（例如）解析JSON。

您可以通過刪除不可變數據的要求來解決問題。如果您將其他房間的鏈接轉換爲OCaml引用（可變字段），則可以像構建JavaScript的命令部分那樣構建循環結構。

使這項工作的一種方法可能是使用room_exits而不是列表的數組。 OCaml數組是可變的。

下面是一些代碼，創建超過3個節點的完全圖（對於僅包含相鄰節點微不足道的節點類型）：

# type node = { nabes: node array };; 
type node = { nabes : node array; } 
# type graph = node list;; 
type graph = node list 
# let z = { nabes = [||] };; 
val z : node = {nabes = [||]} 
# let temp = Array.init 3 (fun _ -> { nabes = Array.make 2 z});; 
val temp : node array = 
    [|{nabes = [|{nabes = [||]}; {nabes = [||]}|]}; 
    {nabes = [|{nabes = [||]}; {nabes = [||]}|]}; 
    {nabes = [|{nabes = [||]}; {nabes = [||]}|]}|] 
# temp.(0).nabes.(0) <- temp.(1);; 
- : unit =() 
# temp.(0).nabes.(1) <- temp.(2);; 
- : unit =() 
# temp.(1).nabes.(0) <- temp.(0);; 
- : unit =() 
# temp.(1).nabes.(1) <- temp.(2);; 
- : unit =() 
# temp.(2).nabes.(0) <- temp.(0);;   
- : unit =() 
# temp.(2).nabes.(1) <- temp.(1);; 
- : unit =() 
# let k3 : graph = Array.to_list temp;; 
val k3 : graph = 
    [{nabes = 
    [|{nabes = [|<cycle>; {nabes = [|<cycle>; <cycle>|]}|]}; 
     {nabes = [|<cycle>; {nabes = [|<cycle>; <cycle>|]}|]}|]}; 
    {nabes = 
    [|{nabes = [|<cycle>; {nabes = [|<cycle>; <cycle>|]}|]}; 
     {nabes = [|{nabes = [|<cycle>; <cycle>|]}; <cycle>|]}|]}; 
    {nabes = 
    [|{nabes = [|{nabes = [|<cycle>; <cycle>|]}; <cycle>|]}; 
     {nabes = [|{nabes = [|<cycle>; <cycle>|]}; <cycle>|]}|]}] 

也可以通過中間結構連接解決問題。例如，您可以有一個將房間名稱映射到房間的字典。然後，您到其他房間的鏈接可以使用名稱（而不是直接鏈接到OCaml值）。過去我使用過這種方法，它運行得很好。 （這一點，事實上，你怎麼JSON工作含蓄。）

Answer 2

這就是爲什麼在以前的答案，我把功能room_exits到Game接口，不進Room。這背後的直覺是房間出口，即其他房間，不是房間的一部分。如果你定義了一些結構，比如「房間是牆壁，寶藏和其他房間」，那麼你定義的不僅僅是一個房間，這基本上意味着你定義了整個迷宮。所以房間只是一個房間，即它的內容。房間的連接方式是Maze。 （我在前面的回答中使用了Game，但也許Maze是一個更好的名字）。

總之，你的具體情況，你只需要從房間數據表示刪除對其他房間的引用，以及迷宮信息存儲爲maze（或game）數據結構內部的關聯容器：

type exits = (dir * room) list 

type maze = { 
    ... 
    entry : room; 
    rooms : exits Room.Map.t 
} 

，或者甚至更精確，你可以使用Dir.Map作爲一個關聯容器，而不是聯想名單：

type exits = room Dir.Map.t 

後者表示保證是t這裏每個方向不超過一個房間。

注：以上定義假定Room實現Comparable接口，並且您使用Core庫。 （我想你自從我記得在課程頁面上有一個與RWO的鏈接）。要實現可比較的接口，您需要實現compare函數和Sexpable接口。它使用型發生器是容易的，基本上它看起來像這樣：

module Room = struct 
    type t = { 
    name : string; 
    treasures : treasure list; 
    ... 
    } with compare, sexp 

    include Comparable.Make(struct 
    type nonrec t = t with compare, sexp 
    end) 
end 

的with compare, sexp將自動生成compare功能，並且對sexp_of_t，t_of_sexp功能，即需要用於一個Comparable.Make算符實現Comparable接口。

注意：如果在這一點上當然太多，那麼你可以使用String.Map.t數據結構，並執行查找房間名稱。這不是一個壞主意。