Пролог - создайте третий отсортированный список из двух уже отсортированных списков

Question

Я пытаюсь получить третий отсортированный список из двух уже отсортированных списков в Прологе. Алгоритм следующий: 1. Сравните главы двух списков 1.1, если первое меньше или равно второму, вставьте его в третий список, а затем удалите его из первого списка. 1.2 иначе вставьте заголовок второго списка в третий и удалите его из второго. 2. повторяйте эти шаги, пока один список не станет пустым.

Теоретически это должно работать, но кое-что мне не хватает.

Вот мой код:

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.

Answer 1

Я думаю, вы неправильно понимаете, как ведут себя переменные Пролога.После того, как вы присвоите значение переменной (термин «унифицировать»), вы никогда не сможете его изменить.Поэтому, когда вы присваиваете значение [H1] для L1 (довольно сложным способом, используя append), другой insSort не может использовать его для возврата результата.Способ исправить ваш код будет выглядеть следующим образом:

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

Таким образом, L будет [H1|L1], где мы знаем значение H1, и мы собираемся вычислитьзначение L1 через некоторое время путем повторного вызова insSort.

Кроме того, здесь нет необходимости использовать append, что-то вроде L = [H1|L1] будет достаточно.