What's wrong with my tree traversal code?

Question

I have a simple tree, defined thusly:

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

I can get a collection of leaf nodes (rooms in my tree "dungeon") like this, and it seems to work:

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

But now I'm trying to get sister leaf node rooms so I can connect them with corridors, and I'm failing miserably (as I often do). Here's my attempt:

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!"

I just end up with an empty seq. Anyway, this all hurts my brain, and I know it's unlikely anyone will slog through it, but I figured it wouldn't hurt to ask.

this is just a guess.. should you be using yield! when you recursively call getCorridors. This will combine the multiple returned sequence elements into your single sequence — Jimmy, Feb 26 '11 at 09:15
Tree is not the right structure to organize rooms. What you need is graph. That could be some simple container, like array or list of rooms, but each room should have all possible exits that lead to other rooms in the same container. Those exits could be organized in a map, with key combined from room and type of exit (north, east, south, west, up, down... add more if you like), and a value being another room. — Dialecticus, Feb 26 '11 at 09:39
You have omitted makeCorridor, could the empty seq be coming from there? — Robert Jeppesen, Feb 26 '11 at 10:02

score 4 · Accepted Answer · answered Feb 26 '11 at 10:24

As Robert commented, maybe your makeCorridor function needs some attention. I've adapted your code, making my own makeCorridor function and replacing Rect by int.

I've used an active pattern to determine when a BspTree is a room. I've also used yield! sequence instead of for x in sequence -> x. These modifications result in the same behavior. I just wanted to show what an active pattern can do:

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 }

Example:

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)))

Result in FSI:

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

What's wrong with my tree traversal code?

1 Answers1

Linked