data-structures - 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

但是，room 有一个“exit”字段，它本身就是一个“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 的隐式工作方式。)