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
– lurker, Commented Jul 2, 2018 at 13:47
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
– lurker, Commented Jul 2, 2018 at 13:57
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
– Jan LovĹˇin, Commented Jul 2, 2018 at 14:22
Remember the recursive call also has a choice of matching either the first predicate clause or the second. — lurker
– lurker, Commented Jul 2, 2018 at 14:50

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

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]

Ok I somehow get it, although coming up with the solution seems harder than understanding it. Btw... since this recursion ends, does it end because [H|T] tries to split [] into 2 parts but it can't?
You may say that, but I think when learning prolog you should think and talk in terms of prolog. In my opinion you should say that prolog backtracking possible solutions for your query (not just doing recursion). It starts backtracking after finding L=[1,2,3] (after fact(1)) While backtracking, the last query insert(1,[],T2) is satisfied (returned true), so no more backtracking needed. (btw remember to pick an answer by pressing the V icon near the votes so it turn green)

Collectives™ on Stack Overflow

Prolog simple recursion

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related