I'm a total beginner on Prolog. There is a posted solution for a homework, and I want to learn how it works, step-by-step. I can't seem to wrap my head around this language. What we were supposed to do was to write a predicate "insert" which places elements in a list like so:
?- insert(Item, [Zero, One, Two], L).
L = [Item, Zero, One, Two] ;
L = [Zero, Item, One, Two] ;
L = [Zero, One, Item, Two] ;
L = [Zero, One, Two, Item] ;
false.
The solution in the knowledge base was:
insert(I, L, [I|L]).
insert(I, [H|L], [H|L2]) :- insert(I, L, L2).
I understand the first line, where L does indeed equal to [Item, Zero, One, Two] because "I" prepends the list, makes sense. Though I'm stumped mainly on the second line, but I really want to learn the processes of it.
The two lines go hand-in-hand, so should be considered together:
insert(I, L, [I|L]).
insert(I, [H|L], [H|L2]) :- insert(I, L, L2).
On the 2nd line: the H is in both lists, as the first element, so is ensuring by unification that the first element of both lists is the same.
H is then missing from the recursive call - this is iterating through the elements of the list, starting at the first element, and dropping the currently-first element each time. So, the current position in the list shifts to the right each time.
When the first line is executed, it can succeed by unifying the third argument as a list consisting of I followed by L (the variables used are commonly H and T, meaning the head of a list and its tail), where L could have come from the 2nd line.
Prolog reassembles the dropped elements of the list, and reports success, whilst noting that there is a choicepoint remaining, i.e. the alternative of entering the 2nd line.