I am trying something rudimentary for a BFS using pattern matching. Here is the example:
type 'a tree =
| Node of 'a * 'a tree * 'a tree
let t =
Node(1, Leaf, Leaf),
Node(3, Leaf, Leaf)
Node(6, Leaf, Leaf),
Node(7, Leaf, Leaf)
let rec bdd t q = match t with
| Leaf → “”
| Node (i,t1,t2) → let w,(),() = (Queue.pop q,Queue.add t1 q, Queue.add t2 q) in string_of_int(i)^" "^bdd w q
let q1 = Queue.create()
let () = Queue.add t q1
let ss = bdd t q1
let () = print_string ss
The output I expected was 4 2 5 1 3 6 7. The output I get is 4 4 2 5 2 5 1 3 6 7 1 3 6 7
Note: I took the tree example from here: 3.11. Example: Trees — OCaml Programming: Correct + Efficient + Beautiful
I am trying to use the builtin queue for BFS - to simply learn more
You should not take at the same time the queue
q and the tree
t. It looks like you are mixing two things, the traversal of a tree and a BFS of the tree.
As if you were to write it with a while loop, your base case should be when your queue is empty, not when you encounter a
Leaf (in that case, just do not add anything to
q but still call yourself recursively, maybe there are still trees in the queue). So your function should look something like:
let rec bdd q =
if Queue.is_empty q then (* do something in the base case *)
else match Queue.pop q with
Leaf -> bdd q
| Node (i, t1, t2) ->
Queue.add t1 q;
Queue.add t2 q;
(* do something with i *)
Other things are wrong with your code. First, the order of evaluation of a tuple is unspecified, you should not write
(e1, e2, e3) where the expressions perform side-effects (since it so happens that in practice
e3 will be evaluated first and
e1 last). You should use
let in to evaluate them in the correct order.
Furthermore here, the two
(), you can just put them in sequence with a
Lastly concatenating strings might become inefficient. You should rather use a
Buffer.t and append to it while performing your BFS (but this may become irrelevant if you are just building the string to debug your function).
Thanks for replying. This definitely solves the issue, but the following is not clear to me. I try with this modification:
| Node (i,t1,t2) -> let w = Queue.pop q in Queue.add t1 q; Queue.add t2 q; string_of_int(i)^" "^(bdd w q)
To ensure that they happen in sequence, still, I see the output 4 4 2 5 2 5 1 3 6 7 1 3 6 7. What is making this repeat twice?
I don’t know how you modified the whole function, but you should not pop the queue after the
Otherwise you are processing the original tree twice, hence the behavior you observe. If you look at your original code, let’s call
t0 the whole example tree.
- you create a queue
q and add
t0 to it. Then you call
bdd t0 q
bdd you match on
t0 so you will add it subtrees to the queue
- in the
Node ... -> branch, you pop from the queue (hence
w is again
t0) and you call
bdd w q.
So clearly your function is called twice on the root of the tree which is wrong.
Thanks for explaining that - makes full sense now.
Also, I had a question about using the buffer_t to concatenate strings. Could please share a link where I can learn more about it?
You can look at the documentation for the
Buffer module here. It is similar to Java’s