43 lines
1.6 KiB
Perl
43 lines
1.6 KiB
Perl
|
%% Exercise 3.5
|
||
|
|
%%
|
||
|
|
%% Binary trees are trees where all internal nodes have exactly two
|
||
|
|
%% children. The smallest binary trees consist of only one leaf node. We
|
||
|
|
%% will represent leaf nodes as `leaf(Label)`. For instance, `leaf(3)`
|
||
|
|
%% and `leaf(7)` are leaf nodes, and therefore small binary trees. Given
|
||
|
|
%% two binary trees B1 and B2 we can combine them into one binary tree
|
||
|
|
%% using the functor `tree/2` as follows: `tree(B1,B2)`. So, from the
|
||
|
|
%% leaves `leaf(1)` and `leaf(2)` we can build the binary tree
|
||
|
|
%% `tree(leaf(1),leaf(2))` . And from the binary trees
|
||
|
|
%% `tree(leaf(1),leaf(2))` and `leaf(4)` we can build the binary tree
|
||
|
|
%% `tree(tree(leaf(1), leaf(2)),leaf(4))`.
|
||
|
|
%%
|
||
|
|
%% Now, define a predicate `swap/2`, which produces the mirror image of
|
||
|
|
%% the binary tree that is its first argument. For example:
|
||
|
|
%%
|
||
|
|
%% ```
|
||
|
|
%% ?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
|
||
|
|
%% T = tree(leaf(4), tree(leaf(2), leaf(1))).
|
||
|
|
%% yes
|
||
|
|
%% ```
|
||
|
|
|
||
|
|
|
||
|
|
%% Let's start with the base case: swapping a leaf is the identity.
|
||
|
|
swap(leaf(X), leaf(X)).
|
||
|
|
|
||
|
|
%% What does it mean to swap a tree? Given a tree
|
||
|
|
%% tree(X, Y)
|
||
|
|
%% it should have an equivalent
|
||
|
|
%% tree(swap(Y), swap(X))
|
||
|
|
%% How do we express this?
|
||
|
|
%% Let's start with a tree made of two leaves.
|
||
|
|
%% swap(tree(X, leaf(Y)), tree(leaf(Y), Z).
|
||
|
|
|
||
|
|
%% But this isn't quite right, is it? We need to express that
|
||
|
|
%% the X node needs to be swapped. So we need to express this
|
||
|
|
%% as a rule.
|
||
|
|
swap(tree(X, leaf(Y)), tree(leaf(Y), Z)) :- swap(X, Z).
|
||
|
|
|
||
|
|
%% And there it is:
|
||
|
|
%% ?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
|
||
|
|
%% T = tree(leaf(4), tree(leaf(2), leaf(1))).
|