Extract the minimum value of a Prolog tree

Question

I'm a very Prolog beginner, so this question might be and become useless, anyway I have defined a Prolog tree as follows:

type([null, tree(T, tree(T), tree(T))]:tree(T)).  

which means that a tree is either null or has a left subtree and a right subtree.
I have then defined a predicate that should output the minimum node value of that tree, which is:

pred(min(tree(T), integer)).
%% (++ --)
pred(calc_min(integer, integer, integer, integer)).
%% (++, ++, ++, --)

    min(tree(Root, null, null), Root).
    min(tree(Root, Left, Right), Result):-
        min(Left, LeftRes),
        min(Right, RightRes),
        calc_min(Root, LeftRes, RightRes, Result).

I think I have to define the base clause where the tree is the null tree, but I don't know what to output.

Answer 1

Oh, nice tree. It is easy to get min of tree but if you want to really get it you need other predicate to help first predicate find min of tree.

min(tree(X, L, _R), Min) :- min_helper(L, X, Min).
min_helper(null, X, X).
min_helper(tree(X, L, _R), _X0, Min) :- min_helper(L, X, Min).

But this only work if binary tree is search tree. Is your tree binary search tree? If not binary tree then not so easy to get min of tree. But you make it difficult because you want min of value AND left min AND right min but this is too difficult. But you say is integer tree so again not so difficult.

min(null, null).
min(tree(X, L, R), Min) :-
    min(L, LMin),
    min(R, RMin),
    min_with_null(X, LMin, Min0),
    min_with_null(Min0, RMin, Min).

min_with_null(X, Maybe_null, Min) :-
    (   Maybe_null == null
    ->  Min = X
    ;   Min is min(X, Maybe_null)
    ).

But what is min of null?

?- min(null, Min).
Min = null.

I check if null but I no check if integer because you write something and it says is integer. But are you sure?

And what is min of some other tree?

?- min(tree(1, null, null), Min).
Min = 1.

?- min(tree(1, tree(0, null, null), null), Min).
Min = 0.

?- min(tree(0, tree(1, null, null), null), Min).
Min = 0.

?- min(tree(1, null, tree(0, null, null)), Min).
Min = 0.

?- min(tree(0, null, tree(1, null, null)), Min).
Min = 0.

?- min(tree(1, tree(2, null, null), tree(3, null, null)), Min).
Min = 1.

Did I forget test case? I don't know.