Что случилось с моим кодом обхода дерева?

Question

У меня есть простое дерево, определяется таким образом:

type BspTree = 
    | Node of Rect * BspTree * BspTree 
    | Null 

я могу получить коллекцию листьев узлов (комнаты в моем дереве «темнице»), как это, и это похоже на работу:

let isRoom = function 
    | Node(_, Null, Null) -> true 
    | _ -> false 

let rec getRooms dungeon = 
    if isRoom dungeon then 
     seq { yield dungeon } 
    else 
     match dungeon with 
     | Node(_, left, right) -> 
      seq { for r in getRooms left -> r 
        for r in getRooms right -> r } 
     | Null -> Seq.empty 

Но теперь я пытаюсь получить комнаты с узлами сестринского листа, чтобы я мог соединить их с коридорами, и я терплю неудачу (как это часто бывает). Вот моя попытка:

let rec getCorridors dungeon = 
    match dungeon with 
    | Null -> failwith "Unexpected null room" 
    | Node(_, left, right) -> 
     match left, right with 
     | Null, Null -> Seq.empty 
     | Node(leftRect, _, _), Node(rightRect, _, _) -> 
      if isRoom left && isRoom right 
      then seq { yield makeCorridor leftRect rightRect } 
      else seq { for l in getCorridors left -> l 
         for r in getCorridors right -> r } 
     | _ -> failwith "Unexpected!" 

Я только что закончил с пустой секцией. В любом случае, это все больно моему мозгу, и я знаю, что маловероятно, что кто-то прольет его, но я подумал, что это не помешает спросить.

Answer 1

Как заметил Роберт, возможно, ваша функция makeCorridor требует некоторого внимания. Я адаптировал ваш код, создав собственную функцию makeCorridor и заменив Rect на int.

Я использовал активный шаблон, чтобы определить, когда BspTree является комнатой. Я также использовал yield! sequence вместо for x in sequence -> x. Эти изменения приводят к одинаковому поведению. Я просто хотел показать, что активный шаблон может сделать:

type BspTree = 
    | Node of int * BspTree * BspTree 
    | Null 

let (|IsRoom|_|) dungeon = 
    match dungeon with 
    | Node(_,Null,Null) -> Some dungeon 
    | _ -> None 

let rec getRooms = function 
    | IsRoom dungeon -> Seq.singleton dungeon 
    | Null -> Seq.empty 
    | Node (_, left, right) -> seq { yield! getRooms left 
            yield! getRooms right } 

let makeCorridor leftNode rightNode = 
    match leftNode, rightNode with 
    | Node(left,Null,Null), Node(right,Null,Null) -> 
     sprintf "(%d) -> (%d)" left right 
    | _ -> failwith "Illegal corridor!" 

let rec getCorridors = function 
    | Null -> failwith "Unexpected null room" 
    | Node(_, Null, Null) -> Seq.empty 
    | Node(_, IsRoom left, IsRoom right) -> seq { yield makeCorridor left right } 
    | Node(_, left, right) -> seq { yield! getCorridors left 
            yield! getCorridors right } 

Пример:

let dungeon = 
    Node(1, Node(2, Node(4,Null,Null), 
        Node(5,Node(8,Null,Null), 
          Node(9,Null,Null))), 
      Node(3, Node(6,Null,Null), 
        Node(7,Null,Null))) 

Результат в FSI:

> getCorridors dungeon;; 
val it : seq<string> = seq ["(8) -> (9)"; "(6) -> (7)"]