Binary search tree: min element

Question

I tried to search for this but without luck; please let me know if the question has been answered!

Assuming I have a binary tree with key-value pairs of the form:

• t/0: the empty tree
• t/4: a tree node with t(Key, Value, Left, Right)

Now I want to get the first (min) element. The obvious (to me) implementation was:

min0(t(K,V,t,_), K, V) :- !.
min0(t(_,_,L,_), K, V) :- min0(L, K, V).

The implementation in SWI-Prolog's library(assoc) however is along the lines of:

min(t(K,V,L,_), Key, Val) :- min(L, K, V, Key, Val).
min(t,K,V,K,V).
min(t(E,K,V,_), _, _, Key, Val) :- min(L, K, V, Key, Val).

Other operations like max and get show the same difference in approach.

Why? What am I missing here? As far as I can see, my version is not creating choice points. But then again, I need a cut in the base case.

Answer 1

Your version does create a choice-point when the clauses are considered for execution. !/0 cuts the previously created choice point away. Your version does not allow indexing on the first argument but relies on a unification at a deeper place in the term. Did you already benchmark the two version on a large binary tree? Other than that, I find the SWI version more elegant because the two cases of tree terms which you mention naturally occur in it.