CODEWITHSUNDEEP
recursionprolog
URL87
URL87

Reputation: 11012

Recursion and lists in Prolog

Having list append implementation in Prolog -

append([],X,X). 
append([H|T1],X,[H|T2]) :- 
    append(T1,X,T2).

Which gives on - 

append([a,b,c],[d,e,f],X).

The output - 

X = [a,b,c,d,e,f].

I wonder how does it work , I tried to trace function calling but I didn't understand how T2 , which is the tail of a list , can be has as tail of X which in append([a,b,c],[d,e,f],X) calling had not defined yet . Can you clear up this recursion for me ?

Upvotes: 4

Views: 252

Answers (1)

Vincent Ramdhanie
Vincent Ramdhanie

Reputation: 103135

It comes down to how Unification works in Prolog. Basically:

  • atoms unify only when they are identical
  • variables unify with anything and
  • compounds unify when each component can unify

So you call: append([a, b, c], [d, e, f], Y) which is your first goal. Note that just to make things easier to see I changed your variable name from X to Y.

This has to be unified with a fact or a rule: Let us see if it will unify with append([], X, X)?

      (1)  append([a, b, c], [d, e, f], Y)
      (2)  append([], X, X)

Both (1) and (2) has the same functor (append) so that is good, and they both have 3 arguments so that is also good. But to unify each corresponding argument must unify. So the first list [a, b, c] in (1) will attempt to unify with the empty list in (2) but they cannot because the list in (1) is not an empty list. So unification fails.

We can then try to unify with append([H|T1],X,[H|T2]).

      (1)   append([a, b, c], [d, e, f], Y)
      (2)   append([H|T1],X,[H|T2])

This time the list [a, b, c] in (1) will attempt to unify with the list [H|T1] in (2). To make this possible the variable H can bind with the atom a (H -> a) and the list T1 can bind with the tail of the list in (1), T1 -> [b, c]. So the first argument works so what we have is:

      (1)   append([a, b, c], [d, e, f], Y)
      (2)'   append([a, b, c],X,[a|T2])

The second argument will also unify because X is a variable and will bind to anything. X -> [d, e, f] so we have:

      (1)   append([a, b, c], [d, e, f], Y)
      (2)''   append([a, b, c],[d, e, f],[a|T2])

And finally the last argument unifies because Y -> [a|T2]. So now that it unifies with the head of a rule, we need to work out the body of the rule: We now end up with append([b, c], [d, e, f], T2) as the goal.

Starting from the first fact again we look for the clause that this goal will bind to. By the same explanation above it will not unify with the first clause but will unify with the second with the bindings: H -> b, T1 -> [c], X -> [d, e, f] and T2 -> [b|T2'].

We are left with the goal: append([c], [d, e, f], T2'). Again it does not unify with the first clause and unifies with the second with the bindings: H -> c, T1 -> [], X -> [d, e, f], T2' -> [c|T2''].

The goal is now: append([], [d, e, f], T2'').

Lets see what happens when we try to unify this with clause 1:

     (1)   append([], [d, e, f], T2'')
     (2)   append([],X,X)

The two empty lists unify, X -> [d, e, f] and since T2''->X then T2'' -> [d, e, f]. Now the tricky part is keeping track of the recursive calls so far and now walking back along the recursion to see the final result. recall that T2' -> [c | T2''] so T2' is actually [c, d, e, f]. And recall that T2 -> [b| T2'] so T2 is actually [b, c, d, e, f].

And finally Y -> [a|T2] so Y is [a, b, c, d, e, f]. Since Y is an external variable it is displayed now that the original goal is satisfied.

Upvotes: 2

Related Questions