Prolog simple recursion

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).

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
Jul 2 at 13:47

[1|[2,3]]

[1|2,3]

[2|[3]]

[2|3]

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
Jul 2 at 13:57

insert(1, [2|[3]], L)

insert(1, [2|[3]], [2|T2])

insert(1, [3], T2)

T2 = [1,3]

[2|[1,3]]

L = [2,1,3]

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
Jul 2 at 14:22

Remember the recursive call also has a choice of matching either the first predicate clause or the second.
– lurker
Jul 2 at 14:50

1 Answer
1

insert generates three values

insert

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)

fact(1)

L=[1,2,3]

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

insert(1,[2,3],L)

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].

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

Moreover:

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

insert(1,[2,3],L)

fact(2)

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]

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?
– Jan LovĹˇin
Jul 2 at 15:14

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)
– Dennis Vash
Jul 2 at 15:39

L=[1,2,3]

fact(1)

insert(1,,T2)

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

搜尋此網誌

Fjhtyj