CODEWITHSUNDEEP
sortingprolog
conectionist
conectionist

Reputation: 2934

Prolog - Create a third sorted list from two already-sorted lists

I'm trying to obtain a third sorted list from two already sorted lists in Prolog. The algorithm is the following: 1. Compare the heads of the two lists 1.1 if the first is less or equal to the second, insert it into the third list and then remove it from the first list. 1.2 else, insert the head of the second list into the third and remove it from the second. 2. repeat these steps until one list is empty.

In theory this should work, but there's something I'm missing.

Here's my code:

insSort([],[],[]).
insSort([],L,L).
insSort(L,[],L).
insSort([H1 | T1],[H2 | T2],L) :- H1 =< H2,
                                    append([H1],[],L1),
                                    insSort(T1,[H2 | T2],L1),L=L1,!.

insSort([H1 | T1],[H2 | T2],L) :- append([H2],[],L1),
                                    insSort(T2,[H1 | T1],L1),L=L1.

Upvotes: 1

Views: 750

Answers (1)

svick
svick

Reputation: 244948

I think you misunderstand how Prolog variables behave. After you assign a value to a variable (the term is “unify”), you can't ever change it. So when you assign the value of [H1] to L1 (in a quite complicated way using append), another insSort can't use it to return the result. A way to fix your code would be like this:

insSort([],[],[]).
insSort([],L,L).
insSort(L,[],L).
insSort([H1 | T1],[H2 | T2],L) :- H1 =< H2,
                                  append([H1],L1,L),
                                  insSort(T1,[H2 | T2],L1),!.

insSort([H1 | T1],[H2 | T2],L) :- append([H2],L1,L),
                                  insSort(T2,[H1 | T1],L1).

This way, L is going to be [H1|L1], where we know the value of H1 and we're going to compute the value of L1 in a while by calling insSort again.

Also, there is no need to use append here, something like L = [H1|L1] would suffice.

Upvotes: 3

Related Questions