CODEWITHSUNDEEP
recursionprologtail-recursion
Biohazard
Biohazard

Reputation: 37

Creating a tail recursive drop function in Prolog

I am trying to create a tail recursive drop/3 in prolog. The way tail recursion was taught to us (poorly) doesn't even begin to show me how I need to even tackle this issue.

This is the only thing I have which does not even work and which isn't even tail recursive as far as I am aware. I am at the end of my mental rope, so any help would be appreciated.

drop(N, [], []).
drop(N, [A,As], Bs) :-
   integer(N), 
   N > 0,
   N1 is N - 1,
   Bs is As,
   drop(N1, As, Bs).

Upvotes: 0

Views: 158

Answers (1)

Nicholas Carey
Nicholas Carey

Reputation: 74227

You problems are:

  • [A,As] is a 2-element list (e.g, [ alpha, bravo ]) rather than breaking the list into its head and tail. [ H | T ] when applied to list [a,b,c] yields H being a and T being [b,c].
  • is/2 does arithmetic, so Bs is As doesn't work. . . and if it did, you are unifying with the result: a prolog variable, once unified is no longer variable, and so cannot be reassigned.

So, assuming that you want to implement this drop/3, try this:

drop( _ , []    , [] ) .  % allows `drop(3, [a,b], R)` to succeed
drop( 0 , R     , R  ) .  % dropping the first 0 element from a list returns the same list
drop( N , [_|T] , R  ) :- % otherwise . . .
  integer(N) ,            % - given that N is an integer, and
  N > 0 ,                 % - given that N is positive, then
  N1 is N-1 ,             % - we decrement N, and
  drop( N1, T , R )       % - recurse down, discarding the head (1st element) of the list
  .                       % Easy!

Note that this will fail if you try to remove 3 elements from a 2-element list. It is a simple change to allow that case to succeed.

What makes this tail recursive is that the only state that matters is whats passed between the recursive calls. That means that the stack frame can be reused. And since no new frame as pushed onto the call stack, that essentially turns the recursive function call into iteration.

Upvotes: 1

Related Questions