3

My example is using the append functor:

append([],L,L). 
append([H|T],L2,[H|L3])  :-  append(T,L2,L3).

//append([123],[abc],L3). this is the query

What really confuses me is the [H|L3] list. Form what I read, that takes off the head, so how is that appending it to the list. When it recurses through the list, and starts coming back, how is that appended? Thanks in advance.

Andy
  • 10,553
  • 21
  • 75
  • 125

3 Answers3

5

The notation [H|T] is syntactic sugar for '.'(H, T). So it is a functor with the name . – a single dot and two arguments. Consider:

?- [1,2,3] = [X|L].
   X = 1, L = [2,3].

Here we ask, if there is a solution to the equation [1,2,3] = [X|L]. And, yes, there is exactly one solution which is described with these two answer substitutions. The process of solving this equation is called unification. This process subsumes reading, selecting and writing of data structures. So, you can call this "taking off the head", but you will miss the generality behind. After all:

?- X = 1, L = [2, 3], M = [X|L].
   X = 1, L = [2,3], M = [1,2,3].

Here we constructed a new list out of a smaller one. But what is:

?- M = [X|L].
   M = [X|L].

This answer implies many solutions. For example, all lists of length 1 and longer.

Since you are looking at append/3, consider the following queries:

?- append(Xs, Ys, [X,Y,Z]).
?- append(Xs, Xs, Zs).
?- append(Xs, Ys, Zs)

More on list syntax.

false
  • 10,264
  • 13
  • 101
  • 209
  • Ahh, I see what you are saying now. Reading the three answers is helping me slowly understand it. Thank you very much. So the list isn't taken apart, but rather unified in a different variable, hence allowing that other one to use the number or list. When using the pipe character again, it also appends them together. Am I understanding you correctly? I really appreciate the help! – Andy Apr 25 '12 at 19:07
  • 1
    @Andy: Yes! As a nit: it is not the pipe character alone, but `[` and `|` and `]` which make the list constructor. The `|` alone is something entirely different. – false Apr 25 '12 at 19:45
3

You can use trace/0 in those cases when you wonder what the execution looks like.

Here is an overview of it.

  • You call append([1, 2, 3], [a, b, c], L3).
  • [1, 2, 3] is not empty, the second clause is applied
  • It calls append([2, 3], [a, b, c], L4). and remembers that the head of L3 is like the head of [1, 2, 3] and that the tail of L3 is L4
  • [2, 3] is not empty, the second clause is applied
  • It calls append([3], [a, b, c], L5). and remembers that the head of L4 is like the head of [2, 3] and that the tail of L4 is L5
  • [3] is not empty, the second clause is applied
  • It calls append([], [a, b, c], L6). and remembers that the head of L5 is like the head of [3] and that the tail of L5 is L6
  • [] unifies with [], the first clause is applied
  • It says that L6 unifies with [a, b, c]

Now Prolog has all the informations to answer you:

L6 = [a, b, c],
L5 = [3|L6],
L4 = [2|L5],
L3 = [1|L4].

will allow Prolog to conclude L3 = [1, 2, 3, a, b, c].

Hope it helped.

m09
  • 7,490
  • 3
  • 31
  • 58
  • Wow, I see what you are saying while at the same time still lost! Sorry. I really want to get it, I'm just finding it hard to conceptualize in my head. So I get what you mean by unifying H, which makes sense. So when it calls itself recursively, the head of [1,2,3] is now also the head of L3, hence [H|L3] (hopefully this is what it means). Now what my question would be is does prolog connect [H|L3] in some way as to remember this? How does it do this: "remembers that the head of L3 is like the head of [1, 2, 3] and that the tail of L3 is L4" happen? I really appreciate the help! – Andy Apr 25 '12 at 19:02
  • @Andy: well, it just calls itself with a list of the form [1|L4] as the last argument where L4 is a free variable, see my little résumé at the end, it's really what happens! – m09 Apr 25 '12 at 19:06
  • Lets assume it only recurses once to simplify my example. When it finishes with that last one, and its going back up the recursion, looking at my example with the L3, does that unify it back to the head of the rule, which is how its constructing L3 after proving L3 on the body side? – Andy Apr 25 '12 at 19:14
  • nah it's a one pass thing, when passing the first time L3 is bound to [1|L4] and then when going through the predicate again L4 is bound to [a, b, c] so now L3 is [1, a, b, c] (that was in the case append([1], [a, b, c], L3). – m09 Apr 25 '12 at 19:18
1

In Prolog, you never do anything quite as active as "takes off"; it might be better to think about it as "focusing on". (Prolog is declarative in nature; you don't say what to do, you say what something looks like.) For example, a list may either be empty ([]) or nonempty ([H|T]); every nonempty list has a head H and a tail T, and | simply lets you to refer to them. Unification may use the declaration of a list as [H|T] to take a list apart or to put a list together, as required.

geekosaur
  • 59,309
  • 11
  • 123
  • 114
  • I see what you are saying. So it isn't really taking it apart, but just declaring them inside of H and T? Am i understanding you correctly? – Andy Apr 25 '12 at 19:04
  • The key is that you are describing, not doing. [H|T] describes a nonempty list in terms of its components (a head and a tail), and describing it that way lets unification use that description to put a list together or take it apart as needed. So yes, it's just declaring them. Working with Prolog takes some getting used to, since you can't just do something, you need to describe what it looks like and let unification use that description to find a set of values which fit it. – geekosaur Apr 25 '12 at 19:20
  • I really appreciate the advice! – Andy Apr 25 '12 at 19:23