Mirror binary tree in Prolog

Question

What I have...

tree(nil).
tree(b(Left,_,Right)) :-
    tree(Left),
    tree(Right).

mirror(b(Left,Head,Right), NewTree) :-
    mirror(Left,NewLeft),
    mirror(Right,NewRight),
    NewTree = b(NewRight,Head,NewLeft).

What I'm querying...

mirror(b(nil,a,b(nil,b,nil)), Result).

Expected result

Result = b(b(nil,b,nil),a,nil).

The tree b(Left,Right,Head) is the first argument of mirror, NewTree is the goal. mirror(Left,NewLeft) recurses through the left side and yields the goal NewLeft, same for Right. NewTree is the tree b(NewRight,Head,NewLeft).

I'm not sure why this isn't working could someone please help.

Answer 1

Based on your current code

tree(nil).
tree(b(Left,_,Right)) :-
    tree(Left),
    tree(Right).

mirror(b(Left,Head,Right), NewTree) :-
    mirror(Left,NewLeft),
    mirror(Right,NewRight),
    NewTree = b(NewRight,Head,NewLeft).

you are very close.

As noted in a comment by Steven

You're missing the base case for mirror/2. What should NewTree be when the input tree is nil?

is very helpful.

Before getting to the full working predicate lets clear up a other things.
The predicate for tree is not needed.

tree(nil).
tree(b(Left,_,Right)) :-
    tree(Left),
    tree(Right).

I don't know if you are showing this to shows us that you know how a tree works or what but for others reading this predicate it is not needed for the answer.

That leaves only

mirror(b(Left,Head,Right), NewTree) :-
    mirror(Left,NewLeft),
    mirror(Right,NewRight),
    NewTree = b(NewRight,Head,NewLeft).

A standard style with using a variable that works like an input and output with several usages is for the starting one, append a 0, then for each succeeding use increase the appended number and for the result append nothing.

mirror(b(Left0,Head,Right0), NewTree) :-
    mirror(Left0,Left),
    mirror(Right0,Right),
    NewTree = b(Right,Head,Left).

Next =/2 is just doing unification. This can be refactored as such

mirror(b(Left0,Head,Right0), b(Right,Head,Left)) :-
    mirror(Left0,Left),
    mirror(Right0,Right).

Now back to your problem

Since a tree is a recursive structure, it can be processed with with recursion. Predicates that work on recursive data structures need a base clause and a clause to do the recursion. You already have a clause to do the recursion but just need a base clause.

If you use the SWI-Prolog gui tracer on your code for the query

mirror(b(nil,a,b(nil,b,nil)), Result).

you will see

that when one of the branches is just nil there is no mirror/2 rule to handle this case.

Adding

mirror(nil,nil).

will solve your problem.

?- mirror(b(nil,a,b(nil,b,nil)), Result).
Result = b(b(nil, b, nil), a, nil).

The entire predicate.

mirror(nil,nil).

mirror(b(Left0,Head,Right0), b(Right,Head,Left)) :-
    mirror(Left0,Left),
    mirror(Right0,Right).