0

I have been stuck on this problem for a couple of days. So given a balanced tree of the form t(Tree, Value, Tree), I want to find the depth of the left tree, which I did with the following code:

depthLeft(nil, 1).
depthLeft(t(Tree1, _, _), N) :-
    depthLeft(Tree1, N1),
    N is N1 + 1.

So the code works but I'm very confused at the counter. Firstly why can't you put the counter above the recursive call? Secondly why can't you argue that N1 is N - 1 instead like here to return the nth element of a list:

element_at(X,[X|_],1).
element_at(X,[_|L],K) :- K > 1, K1 is K - 1, element_at(X,L,K1).

I fail to see why the counters have a different logic here. If anyone could point me in the direction it would be greatly appreciated.

false
  • 10,264
  • 13
  • 101
  • 209
LLScheme
  • 73
  • 7
  • `Firstly why can't you put the counter above the recursive call?` Because `N1` is not bound to a numeric value. In theory Prolog is a declarative language and should allow for this but the use of is/2 breaks that agreement. Constraints might work in this case but I have not tested it so take with a grain of salt. – Guy Coder Jan 01 '23 at 12:28
  • `Secondly why can't you argue that N1 is N - 1 instead like here to return the nth element of a list` Same reason as other answer. `K` is bound to a numeric value before use. – Guy Coder Jan 01 '23 at 12:30
  • This question is most likely a duplicate and should be closed. – Guy Coder Jan 01 '23 at 12:31
  • 2
    Efficient alternative: "accumulator" - see e.g. https://stackoverflow.com/questions/19944969/prolog-accumulators-are-they-really-a-different-concept – brebs Jan 01 '23 at 13:45

1 Answers1

1

Firstly why can't you put the counter above the recursive call?

Because it doesn't work if you do that; Prolog isn't magic, it functions in a way that works on real computers, a way that was simple enough for computers of the 1970s - line by line, from the top:

depthLeft(t(Tree1, _, _), N) :-    % this holds if
    N is N1 + 1.                   % (calculate N1 + 1, error, N1 has no value).
    depthLeft(Tree1, N1),          % stopped before getting here.

Secondly why can't you argue that N1 is N - 1 instead like here to return the nth element of a list:

That goes the other way, you provide K as the index of the element you desire so K-1 can be calculated as soon as that code is reached. If you want to feed in "does my tree have depth 4?" then you can rearrange so N1 can have a value but that's a different question to "what is the depth of my tree?".

You either count from zero, increasing as you descend into the tree, stopping at the end, in a tail recursive way (no remaining work), and return the final count. Or you descend into the tree knowing nothing, pending the addition work for later until you reach to the end, count 1 there, then ascend back out through the callstack doing all the pending additions until you get back to the start with your answer. This way is often simpler to write but eats more memory and performs worse.

TessellatingHeckler
  • 27,511
  • 4
  • 48
  • 87