Prolog simple recursion

Question

This is a really simple quesiton but I don't get it.

insert(X, L, [X|L]).
insert(X, [H|T], [H|T2]) :-
    insert(X, T, T2).

We run it with insert(1, [2,3], L).

When it's called the 1st insert produces (1, [2,3], [1|2,3]) > L = [1,2,3], then it looks at the second insert(1, [2|3], [2|T2]) // T2 is a variable im guessing.. and it calls insert(1, [3], T2) which calls the 1st insert again with insert(1, [3], [1|3]) > L = [1,3],

which is not true, because it actually returns L = [2,1,3]. What am I missing about recursions?

Syntax correction [1|[2,3]] not [1|2,3] and [2|[3]] not [2|3]. — lurker
You neglected to unravel the full recursion in your second example. The call to insert(1, [2|[3]], L) matches the second clause with insert(1, [2|[3]], [2|T2]) which calls insert(1, [3], T2). That call yields T2 = [1,3] as you show, but that leads to the final result [2|[1,3]] or simply L = [2,1,3]. — lurker
Aha ok, so after this example returns, how does it get the 3rd and last result? I'm guessing that when you call the second example it calls the first insert and returns and also calls the second insert(1, [3|[]], [3|T2]) which calls insert(1, [], T2) and T2 = [1] and that would get me [3,1], seems like I don't clearly get it. — Jan LovĹˇin
Remember the recursive call also has a choice of matching either the first predicate clause or the second. — lurker

Dennis Vash Dennis Vash · Accepted Answer · 2018-07-02T14:39:31

insert generates three values

insert(X, L, [X|L]).            %fact(1)
insert(X, [H|T], [H|T2]) :-     %fact(2)
    insert(X, T, T2).

?- insert(1,[2,3],L).
L = [1, 2, 3] ;
L = [2, 1, 3] ;
L = [2, 3, 1].

Lets see how it works:

insert(1,[2,3],L) for fact(1) generates L=[1,2,3]

insert(1,[2,3],L) for fact(2):

insert(1,[2|[3]],[2|T2]) :-
    insert(1,[3],T2) :-             %check fact(1)
        insert(1,[3],[1|[3])        %T2 = [1,3]

so L=[2|T2]=[2,1,3].

Moreover:

insert(1,[2,3],L) for fact(2) generates another value,

insert(1,[2|[3]],[2|T2]) :-
    insert(1,[3],T2) :-             %check fact(2)
        insert(1,[3|[]],[3|T3]) :-  %check fact(2) T2=[3,1]
            insert(1,[],[1])        %check fact(1) T3=[1]

so L=[2|T2]=[2,3,1]

Prolog simple recursion

1 Answers