How do I append lists in Prolog?

Question

How do I append lists in Prolog? I've searched on the Internet and I found this (from http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_7.html)

append([X|Y],Z,[X|W]) :- append(Y,Z,W).   append([],X,X). 

So it gets the Z by removing the elements of [X|Y] in [X|W]. But how do I append two lists together?

Example,

appendlist([1,2],[3,4,5],X). 

The result will be X = [1,2,3,4,5].

Also I don't know what happening in the recursion. (I traced it but didn't understand)

EDIT: What I want to know is how it should be coded to function like the predefined append() in Prolog.

Answer 1

The code as you've posted it is (almost) OK. The order of clauses just needs to be swapped (in order to make this predicate definition productive, when used in a generative fashion):

append( [], X, X).                                   % (* your 2nd line *) append( [X | Y], Z, [X | W]) :- append( Y, Z, W).    % (* your first line *)  

This defines a relationship between the three arguments, let's say A, B and C.

Your first line says, " C is the result of appending A and B if A and C are non-empty lists, they both have the same head (i.e. first element), and the tail of C is the result of appending the tail of A with the same 2nd argument, B".

  a        a   ----------   b        b   c        c   .    d   d        e   e        .   . 

Or from left to right:

         a | b c .            |     d e .          a | b c d e .  append(         [],                   Z,                  Z ).        append( [X | Y   ],                  Z,         [X |         W ] ) :- append(              Y,  Z,  W). 

Think about it, it makes perfect sense. What it does is, we want to define the append/3 relationship, and we know what we want it to be, so we just write down some obvious facts about it that we want it to fulfill, the laws that it must follow if you will.

So assuming we have this code already defined for us, what laws must it follow? Obviously, appending a tail of some list with another list gives us a tail of result of appending the full list with that 2nd list.

This defines how we "slide along" the first list. But what if there's nowhere more to slide? What if we've reached the end of that list? Then we've arrived at the empty list, and appending an empty list with another list gives us that list as the result. Obviously. And that's what that 2nd line in your code is telling us, it says, "appending an empty list with another list produces that list as the result".

Amazingly, having written down these two laws that append/3 must follow, is the same as writing down the definition itself.

addition: this explains it from a declarative point of view; do check out an answer by m09 which shows it more from the operational point of view.