2

这个问题与我之前提出的另一个问题有关。

我正在从 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。这似乎是一种循环类型。

谁能帮我这个？

4

2 回答 2

2

如果您坚持使用 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 是如何隐式工作的。）

于 2015-12-19T23:40:06.077 回答
1

这就是为什么在上一个答案中我将函数room_exits放入Game界面，而不是放入Room. 这背后的直觉是房间出口，即其他房间，不是房间的一部分。如果你定义一些结构，如“房间是墙壁、宝藏和其他房间”，那么你定义的不仅仅是一个房间，这基本上意味着，你正在定义整个迷宫。所以房间，只是一个房间，即它的内容。房间的连接方式是Maze. （我Game在以前的答案中使用过这个，但也许Maze是一个更好的名字）。

总而言之，在您的特定情况下，您只需从房间数据表示中删除对其他房间的引用，并将迷宫信息作为关联容器存储在maze(or game) 数据结构中：

 type exits = (dir * room) list

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

或者更准确地说，您可以将Dir.Map其用作关联容器，而不是关联列表：

type exits = room Dir.Map.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_tt_of_sexpComparable.MakeComparable

注意：如果此时太多了，那么你可以只使用String.Map.t数据结构，并通过房间名称进行查找。这不会是一个坏主意。

于 2015-12-21T15:14:27.217 回答